2906. Construct Product Matrix

📘 題目敘述

給你一個 0-indexed 的二維整數矩陣 grid，大小為 n x m。

如果一個同樣大小的矩陣 p 滿足以下條件，就稱它是 grid 的 product matrix：

• p[i][j] 等於 grid 中除了 grid[i][j] 以外所有元素的乘積
• 最後再對 12345 取模

請回傳 grid 的 product matrix。

條件限制

• 1 <= n == grid.length <= 10^5
• 1 <= m == grid[i].length <= 10^5
• 2 <= n * m <= 10^5
• 1 <= grid[i][j] <= 10^9

🧠 解題思路

這題的想法和一維陣列的「除了自己以外的乘積」很像。

我不直接對每個位置重新把其他所有數都乘一遍，因為那樣太慢。
我改成先把整個矩陣依照 row-major 順序看成一條線，然後預先算好：

• 每個位置前面的乘積
• 每個位置後面的乘積

這樣對某個位置來說：

• 它左邊全部元素的乘積
• 乘上它右邊全部元素的乘積

就等於「除了自己以外所有元素的乘積」。

所以我用兩個陣列：

• f：prefix product
• b：suffix product

最後把兩邊乘起來，就能得到答案。

所有變數

• m：列數
• n：行數
• f：前綴乘積陣列，f[pos] 表示線性化後前 pos 個元素的乘積
• b：後綴乘積陣列，從後面往前累積的乘積
• M：模數 12345
• now：目前累積乘積
• ans：答案矩陣
• pos：目前線性化後的位置索引

🪜 主要流程步驟

1. 先準備前綴乘積和後綴乘積陣列

我這裡先讓 f 和 b 都從一個 1 開始。

這樣之後如果某個位置左邊沒有元素，那它左邊的乘積自然就是 1；
右邊沒有元素時也是同樣概念。

2. 先照 row-major 順序算前綴乘積

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        now *= grid[i][j];
        now %= M;
        f.push_back(now);
    }
}

這一步是在把矩陣攤平成一條線來看。

假設目前走到某個位置時，f 裡就會記住：

• 從最前面開始到目前為止的累積乘積

所以之後如果我想知道某個位置左邊所有元素的乘積，直接看對應的 f[pos] 就可以了。

3. 再從後往前算後綴乘積

這一步和前面對稱，只是改成從矩陣最後一格往前掃。

這樣 b 裡就會記住：

• 從最尾端開始往前的累積乘積

之後某個位置右邊所有元素的乘積，就可以從 b 裡對應拿到。

4. 建立答案矩陣

這裡我重新再走一次矩陣，並用 pos 表示目前這格在線性化後是第幾個位置。

5. 對每個位置，把左邊乘積和右邊乘積乘起來

假設目前位置是 pos，那麼：

• f[pos] 表示它前面所有元素的乘積
• b[m * n - 1 - pos] 表示它後面所有元素的乘積

兩個相乘之後，就剛好是：

• 除了自己以外，所有元素的乘積

最後再 % M，存進答案矩陣。

6. 為什麼這樣剛好排除自己

這裡的關鍵是 f 和 b 的設計方式。

f[pos] 存的是：

• 前 pos 個元素的乘積

所以它不包含第 pos 個元素自己。

而 b[m * n - 1 - pos] 存的是：

• 第 pos 個元素後面那些元素的乘積

所以它也不包含自己。

這樣兩邊乘起來，剛好就是「除了自己以外」的所有元素乘積。

7. 最後回傳答案矩陣

當每個位置都算完之後，ans 就是題目要的 product matrix。

⏱️ 複雜度

設 N = m * n。

• 時間複雜度：O(N)
  我總共掃矩陣三次，每次都是線性。
• 空間複雜度：O(N)
  額外用了 f、b 和答案矩陣。

💻 程式碼實作

class Solution {
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> f(1, 1);
        vector<int> b(1, 1);
        const int M = 12345;
        long long now = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                now *= grid[i][j];
                now %= M;
                f.push_back(now);
            }
        }
        now = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                now *= grid[i][j];
                now %= M;
                b.push_back(now);
            }
        }
        vector<vector<int>> ans(m, vector<int>(n));
        int pos = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                now = f[pos] * b[m * n - 1 - pos];
                now %= M;
                ans[i][j] = now;
                pos++;
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/construct-product-matrix/