构造乘积矩阵

难度: Medium

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

对于每个元素 p[i][j] ，它的值等于除了 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[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。

提示：

1 <= n == grid.length <= 10⁵
1 <= m == grid[i].length <= 10⁵
2 <= n * m <= 10⁵
1 <= grid[i][j] <= 10⁹

Submission

运行时间: 171 ms

内存: 39.9 MB

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        MOD = 12345
        m = len(grid)
        n = len(grid[0])
        res = [[0] * n for _ in range(m)]
        #前缀积
        suf = 1
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                res[i][j] = suf
                suf = (suf * grid[i][j]) % MOD
        #后缀积
        pre = 1
        for i in range(m):
            for j in range(n):
                res[i][j] = (res[i][j] * pre) % MOD
                pre = (pre * grid[i][j]) % MOD
        return res

Explain

题解采用了前缀积和后缀积的概念来计算每个位置上的乘积矩阵值。首先，通过两次遍历来构造乘积矩阵：第一次从矩阵的末尾开始，计算从当前位置到末尾的所有元素的乘积（后缀积），存储在结果矩阵中。第二次从矩阵的开头开始，用一个累积变量（前缀积）乘以当前存储的后缀积并取余，更新到结果矩阵中。这样，每个位置的值即为除当前元素外所有元素的乘积。

时间复杂度: O(k)

空间复杂度: O(k)

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        MOD = 12345  # 定义模数
        m = len(grid)  # 行数
        n = len(grid[0])  # 列数
        res = [[0] * n for _ in range(m)]  # 初始化结果矩阵
        # 后缀积初始化
        suf = 1
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                res[i][j] = suf  # 存储后缀积
                suf = (suf * grid[i][j]) % MOD  # 更新后缀积
        # 前缀积初始化
        pre = 1
        for i in range(m):
            for j in range(n):
                res[i][j] = (res[i][j] * pre) % MOD  # 更新结果矩阵
                pre = (pre * grid[i][j]) % MOD  # 更新前缀积
        return res

Explore

在计算前缀积和后缀积时，确保当前元素grid[i][j]不被包含的关键在于更新积的顺序和应用时机。对于后缀积，首先将当前位置的后缀积存储在结果矩阵中，然后再乘以grid[i][j]更新后缀积。这样，当计算下一个元素的后缀积时，当前元素已经在更新后的后缀积中。前缀积则相反，先用前缀积更新结果矩阵，然后再乘以当前元素。这种处理方式确保在计算某个位置的结果时，该位置的元素不参与乘积运算。

前缀积和后缀积在开始计算时都初始化为1。这是因为乘积的初始状态应为乘法的单位元素，即任何数与1相乘都不会改变。这种初始化方式允许在第一次迭代时正确地引入数组中的第一个或最后一个元素。如果初始化为0，则任何乘法操作的结果都将是0，这会导致错误的输出。

在处理矩阵的边界情况时，前缀积和后缀积的操作并不需要特别的边界处理，因为初始化已经设置了积为1，并且循环覆盖了从第一行到最后一行的所有元素。对于后缀积，从最后一行开始向第一行计算；对于前缀积，从第一行开始向最后一行计算。每次迭代都是独立的，确保了边界行也被正确地处理。

在更新结果矩阵时立即取模12345主要有两个原因：一是防止计算过程中数值过大导致整数溢出，特别是在使用大数据集时；二是模运算可以保持数值在一个合理的范围内，便于处理和存储。此外，取模操作还有助于保持结果的一致性，确保输出结果的稳定性和正确性。