行和列中一和零的差值
难度:
标签:
题目描述
You are given a 0-indexed m x n binary matrix grid.
A 0-indexed m x n difference matrix diff is created with the following procedure:
- Let the number of ones in the
ithrow beonesRowi. - Let the number of ones in the
jthcolumn beonesColj. - Let the number of zeros in the
ithrow bezerosRowi. - Let the number of zeros in the
jthcolumn bezerosColj. diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj
Return the difference matrix diff.
Example 1:
Input: grid = [[0,1,1],[1,0,1],[0,0,1]] Output: [[0,0,4],[0,0,4],[-2,-2,2]] Explanation: - diff[0][0] =onesRow0 + onesCol0 - zerosRow0 - zerosCol0= 2 + 1 - 1 - 2 = 0 - diff[0][1] =onesRow0 + onesCol1 - zerosRow0 - zerosCol1= 2 + 1 - 1 - 2 = 0 - diff[0][2] =onesRow0 + onesCol2 - zerosRow0 - zerosCol2= 2 + 3 - 1 - 0 = 4 - diff[1][0] =onesRow1 + onesCol0 - zerosRow1 - zerosCol0= 2 + 1 - 1 - 2 = 0 - diff[1][1] =onesRow1 + onesCol1 - zerosRow1 - zerosCol1= 2 + 1 - 1 - 2 = 0 - diff[1][2] =onesRow1 + onesCol2 - zerosRow1 - zerosCol2= 2 + 3 - 1 - 0 = 4 - diff[2][0] =onesRow2 + onesCol0 - zerosRow2 - zerosCol0= 1 + 1 - 2 - 2 = -2 - diff[2][1] =onesRow2 + onesCol1 - zerosRow2 - zerosCol1= 1 + 1 - 2 - 2 = -2 - diff[2][2] =onesRow2 + onesCol2 - zerosRow2 - zerosCol2= 1 + 3 - 2 - 0 = 2
Example 2:
Input: grid = [[1,1,1],[1,1,1]] Output: [[5,5,5],[5,5,5]] Explanation: - diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 3 + 2 - 0 - 0 = 5 - diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 3 + 2 - 0 - 0 = 5 - diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 3 + 2 - 0 - 0 = 5 - diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 3 + 2 - 0 - 0 = 5 - diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 3 + 2 - 0 - 0 = 5 - diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 3 + 2 - 0 - 0 = 5
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 105grid[i][j]is either0or1.
代码结果
运行时间: 178 ms, 内存: 37.1 MB
/*
* 思路：
* 1. 计算每一行和每一列中1的数量（onesRow, onesCol）。
* 2. 计算每一行和每一列中0的数量（zerosRow, zerosCol）。
* 3. 使用Java Stream API进行计算和构建差值矩阵。
*/
import java.util.stream.*;
public class Solution {
public int[][] onesMinusZeros(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[] onesRow = new int[m];
int[] onesCol = new int[n];
int[] zerosRow = new int[m];
int[] zerosCol = new int[n];
// 计算每行每列的1和0的数量
IntStream.range(0, m).forEach(i -> {
IntStream.range(0, n).forEach(j -> {
if (grid[i][j] == 1) {
onesRow[i]++;
onesCol[j]++;
} else {
zerosRow[i]++;
zerosCol[j]++;
}
});
});
// 计算diff矩阵
return IntStream.range(0, m).mapToObj(i ->
IntStream.range(0, n).map(j ->
onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j]
).toArray()
).toArray(int[][]::new);
}
}解释
方法:
此题解的核心思路是首先计算每行和每列中1和0的数量。然后根据题目要求的公式 diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj，计算每个位置的差值。具体步骤包括：1. 计算每行一的数目和零的数目。2. 计算每列一的数目和零的数目。3. 使用预计算的行和列的一和零的数目，更新矩阵中的每个元素。
时间复杂度:
O(m * n)
空间复杂度:
O(m + n)
代码细节讲解
🦆
在计算每行每列的1和0的数量时，此算法是否考虑了所有可能的边界情况，例如全0行或全1行？
▷🦆
在更新矩阵`grid[i][j]`时，直接修改原矩阵是否会影响后续的计算？或者算法是如何确保这种直接修改不影响结果的？
▷🦆
题解中使用了转置矩阵来帮助计算列中的1和0的数量，这种方法是否会对空间复杂度产生影响？如果会，如何评估这种影响？
▷