class Solution {
public:
vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
}
};
2906. 构造乘积矩阵
给你一个下标从 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 <= 1051 <= m == grid[i].length <= 1052 <= n * m <= 1051 <= grid[i][j] <= 109原站题解
java 解法, 执行用时: 13 ms, 内存消耗: 69.7 MB, 提交时间: 2023-10-16 20:52:27
class Solution {
public int[][] constructProductMatrix(int[][] grid) {
final int MOD = 12345;
int n = grid.length, m = grid[0].length;
int[][] p = new int[n][m];
long suf = 1; // 后缀乘积
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
p[i][j] = (int) suf; // p[i][j] 先初始化成后缀乘积
suf = suf * grid[i][j] % MOD;
}
}
long pre = 1; // 前缀乘积
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
p[i][j] = (int) (p[i][j] * pre % MOD); // 然后再乘上前缀乘积
pre = pre * grid[i][j] % MOD;
}
}
return p;
}
}
cpp 解法, 执行用时: 212 ms, 内存消耗: 124 MB, 提交时间: 2023-10-16 20:52:11
class Solution {
public:
vector<vector<int>> constructProductMatrix(vector<vector<int>> &grid) {
const int MOD = 12345;
int n = grid.size(), m = grid[0].size();
vector<vector<int>> p(n, vector<int>(m));
long long suf = 1; // 后缀乘积
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
p[i][j] = suf; // p[i][j] 先初始化成后缀乘积
suf = suf * grid[i][j] % MOD;
}
}
long long pre = 1; // 前缀乘积
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
p[i][j] = p[i][j] * pre % MOD; // 然后再乘上前缀乘积
pre = pre * grid[i][j] % MOD;
}
}
return p;
}
};
golang 解法, 执行用时: 164 ms, 内存消耗: 18.8 MB, 提交时间: 2023-10-16 20:51:57
func constructProductMatrix(grid [][]int) [][]int {
const mod = 12345
n, m := len(grid), len(grid[0])
p := make([][]int, n)
suf := 1 // 后缀乘积
for i := n - 1; i >= 0; i-- {
p[i] = make([]int, m)
for j := m - 1; j >= 0; j-- {
p[i][j] = suf // p[i][j] 先初始化成后缀乘积
suf = suf * grid[i][j] % mod
}
}
pre := 1 // 前缀乘积
for i, row := range grid {
for j, x := range row {
p[i][j] = p[i][j] * pre % mod // 然后再乘上前缀乘积
pre = pre * x % mod
}
}
return p
}
python3 解法, 执行用时: 240 ms, 内存消耗: 39.9 MB, 提交时间: 2023-10-16 20:51:46
class Solution:
def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
MOD = 12345
n, m = len(grid), len(grid[0])
p = [[0] * m for _ in range(n)]
suf = 1 # 后缀乘积
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
p[i][j] = suf # p[i][j] 先初始化成后缀乘积
suf = suf * grid[i][j] % MOD
pre = 1 # 前缀乘积
for i, row in enumerate(grid):
for j, x in enumerate(row):
p[i][j] = p[i][j] * pre % MOD # 然后再乘上前缀乘积
pre = pre * x % MOD
return p