构造乘积矩阵1

题目讲解

不能直接把所有数乘起来再除以 grid[i][j]

因为 grid[i][j] 可能为 0，除法不可行。

采用 前缀积 + 后缀积 的操作思路：

前缀积: Prefix[i] = arr[0] * arr[1] * arr[2] * arri-1.

后缀积: suffix[i] = arr[i+1] * arr[i+2] * arrL-1

具体流程

代码

c++
python
java
class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        MOD = 12345
        m, n = len(grid), len(grid[0])

        # 二维数组展开为一维
        arr = [grid[i][j] for i in range(m) for j in range(n)]
        L = len(arr)

        # 前缀积初始化
        prefix = [1] * L
        # 后缀积初始化
        suffix = [1] * L

         # 前缀积
        for i in range(1, L):
            prefix[i] = (prefix[i - 1] * arr[i - 1]) % MOD

        # 后缀积
        # range(start, stop, step).
        # suffix[L-1] 是最后一个元素，它没有右边的数 → 我们已经提前把 suffix[L-1] 设为 1(空积)
        # 所以我们要从 倒数第二个元素 L-2 开始往前算.
        for i in range(L - 2, -1, -1):
            suffix[i] = (suffix[i + 1] * arr[i + 1]) % MOD

        # 计算答案
        ans_arr = [(prefix[i] * suffix[i]) % MOD for i in range(L)]

        # 映射回二维
        ans = [[0] * n for _ in range(m)]
        idx = 0
        for i in range(m):
            for j in range(n):
                ans[i][j] = ans_arr[idx]
                idx += 1

        return ans

链接

  1. 构造乘积矩阵https://leetcode.cn/problems/construct-product-matrix/description/ ↩︎