构造乘积矩阵
难度:
标签:
题目描述
Given a 0-indexed 2D integer matrix grid of size n * m, we define a 0-indexed 2D matrix p of size n * m as the product matrix of grid if the following condition is met:
- Each element
p[i][j]is calculated as the product of all elements ingridexcept for the elementgrid[i][j]. This product is then taken modulo12345.
Return the product matrix of grid.
Example 1:
Input: grid = [[1,2],[3,4]] Output: [[24,12],[8,6]] Explanation: 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 So the answer is [[24,12],[8,6]].
Example 2:
Input: grid = [[12345],[2],[1]] Output: [[2],[0],[0]] Explanation: 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. So p[0][1] = 0. p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0. So p[0][2] = 0. So the answer is [[2],[0],[0]].
Constraints:
1 <= n == grid.length <= 1051 <= m == grid[i].length <= 1052 <= n * m <= 1051 <= grid[i][j] <= 109
代码结果
运行时间: 171 ms, 内存: 39.9 MB
/*
* 思路：
* 1. 使用流来计算所有元素的乘积。
* 2. 使用流来计算每个位置的乘积矩阵值。
*/
import java.util.stream.*;
public class Solution {
public int[][] productMatrix(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] result = new int[n][m];
int mod = 12345;
long totalProduct = Stream.of(grid)
.flatMapToInt(Arrays::stream)
.asLongStream()
.reduce(1, (a, b) -> (a * b) % mod);
IntStream.range(0, n).forEach(i ->
IntStream.range(0, m).forEach(j ->
result[i][j] = (int) ((totalProduct * modInverse(grid[i][j], mod)) % mod)
)
);
return result;
}
private long modInverse(long a, long mod) {
return power(a, mod - 2, mod);
}
private long power(long x, long y, long mod) {
long res = 1;
x = x % mod;
while (y > 0) {
if ((y & 1) == 1)
res = (res * x) % mod;
y = y >> 1;
x = (x * x) % mod;
}
return res;
}
}
解释
方法:
题解采用了前缀积和后缀积的概念来计算每个位置上的乘积矩阵值。首先，通过两次遍历来构造乘积矩阵：第一次从矩阵的末尾开始，计算从当前位置到末尾的所有元素的乘积（后缀积），存储在结果矩阵中。第二次从矩阵的开头开始，用一个累积变量（前缀积）乘以当前存储的后缀积并取余，更新到结果矩阵中。这样，每个位置的值即为除当前元素外所有元素的乘积。
时间复杂度:
O(k)
空间复杂度:
O(k)
代码细节讲解
🦆
在处理前缀积和后缀积时，如何确保不会涉及当前元素grid[i][j]本身的值？
▷🦆
请问如何初始化前缀积和后缀积，以及为什么选择这种初始化方式？
▷🦆
在使用前缀积和后缀积的方法中，如何处理矩阵的边界情况，例如第一行和最后一行？
▷🦆
在更新结果矩阵时为何需要立即取模12345，这样做有什么好处或者必要性？
▷