Medium

题目描述

给你一个大小为 n * m 的下标从 0 开始的二维整数矩阵 grid，定义一个大小为 n * m 的下标从 0 开始的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵：

  • 对于每个元素 p[i][j]，它的值是 grid 中除了 grid[i][j] 以外所有元素的乘积，然后对 12345 取余。

返回 grid 的乘积矩阵。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：[[24,12],[8,6]]
解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]]。

示例 2：

输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[1][0] * grid[2][0] = 2 * 1 = 2。
p[1][0] = grid[0][0] * grid[2][0] = 12345 * 1 = 12345。12345 % 12345 = 0。所以 p[1][0] = 0。
p[2][0] = grid[0][0] * grid[1][0] = 12345 * 2 = 24690。24690 % 12345 = 0。所以 p[2][0] = 0。
所以答案是 [[2],[0],[0]]。

提示：

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

提示：

  • 尝试不使用除法运算来解决这个问题。
  • 创建两个二维数组来保存前缀和后缀乘积，使用它们来计算每个位置的乘积。

解题思路

这是一道经典的除自身以外数组乘积问题的二维版本。我们不能使用除法，因为可能存在零值或者会导致精度问题。

核心思路是使用前缀乘积和后缀乘积的思想：

  1. 对于位置 (i, j)，其乘积等于 该位置之前所有元素的乘积 × 该位置之后所有元素的乘积
  2. 将二维矩阵展开为一维处理，位置 (i, j) 对应一维索引 i * m + j

算法步骤：

  1. 第一次遍历：计算每个位置的前缀乘积（该位置之前所有元素的乘积）
  2. 第二次遍历：从后往前计算后缀乘积，并与前缀乘积相乘得到最终结果
  3. 在计算过程中对 12345 取模避免溢出

这种方法时间复杂度为 O(n×m)，空间复杂度为 O(1)（不计输出数组），是最优解法。

关键优化：

  • 直接在结果数组中存储前缀乘积，节省空间
  • 使用单个变量维护后缀乘积
  • 及时取模防止整数溢出

代码实现

class Solution {
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        const int MOD = 12345;
        vector<vector<int>> result(n, vector<int>(m));
        
        // 第一次遍历：计算前缀乘积
        int prefixProduct = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result[i][j] = prefixProduct;
                prefixProduct = (1LL * prefixProduct * grid[i][j]) % MOD;
            }
        }
        
        // 第二次遍历：计算后缀乘积并更新结果
        int suffixProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                result[i][j] = (1LL * result[i][j] * suffixProduct) % MOD;
                suffixProduct = (1LL * suffixProduct * grid[i][j]) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n, m = len(grid), len(grid[0])
        MOD = 12345
        result = [[0] * m for _ in range(n)]
        
        # 第一次遍历：计算前缀乘积
        prefix_product = 1
        for i in range(n):
            for j in range(m):
                result[i][j] = prefix_product
                prefix_product = (prefix_product * grid[i][j]) % MOD
        
        # 第二次遍历：计算后缀乘积并更新结果
        suffix_product = 1
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                result[i][j] = (result[i][j] * suffix_product) % MOD
                suffix_product = (suffix_product * grid[i][j]) % MOD
        
        return result

public class Solution {
    public int[][] ConstructProductMatrix(int[][] grid) {
        int n = grid.Length, m = grid[0].Length;
        const int MOD = 12345;
        int[][] result = new int[n][];
        for (int i = 0; i < n; i++) {
            result[i] = new int[m];
        }
        
        // 第一次遍历：计算前缀乘积
        long prefixProduct = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result[i][j] = (int)prefixProduct;
                prefixProduct = (prefixProduct * grid[i][j]) % MOD;
            }
        }
        
        // 第二次遍历：计算后缀乘积并更新结果
        long suffixProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                result[i][j] = (int)((result[i][j] * suffixProduct) % MOD);
                suffixProduct = (suffixProduct * grid[i][j]) % MOD;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[][]} grid
 * @return {number[][]}
 */
var constructProductMatrix = function(grid) {
    const n = grid.length, m = grid[0].length;
    const MOD = 12345;
    const result = Array(n).fill(0).map(() => Array(m).fill(0));
    
    // 第一次遍历：计算前缀乘积
    let prefixProduct = 1;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            result[i][j] = prefixProduct;
            prefixProduct = (prefixProduct * grid[i][j]) % MOD;
        }
    }
    
    // 第二次遍历：计算后缀乘积并更新结果
    let suffixProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        for (let j = m - 1; j >= 0; j--) {
            result[i][j] = (result[i][j] * suffixProduct) % MOD;
            suffixProduct = (suffixProduct * grid[i][j]) % MOD;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n×m)，需要遍历矩阵两次
空间复杂度O(1)，除了输出数组外只使用常数级额外空间

相关题目