零矩阵
难度:
标签:
题目描述
Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.
Example 1:
Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ]
Example 2:
Input: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] Output: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]
代码结果
运行时间: 23 ms, 内存: 16.9 MB
/*
* 题目思路：
* 1. 使用stream API实现标记零元素的行和列。
* 2. 然后使用stream API将对应行和列清零。
*/
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class SolutionStream {
public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean[] rowZero = new boolean[rows];
boolean[] colZero = new boolean[cols];
// 标记哪些行和列需要清零
IntStream.range(0, rows).forEach(i -> {
IntStream.range(0, cols).forEach(j -> {
if (matrix[i][j] == 0) {
rowZero[i] = true;
colZero[j] = true;
}
});
});
// 设置对应行列为0
IntStream.range(0, rows).forEach(i -> {
IntStream.range(0, cols).forEach(j -> {
if (rowZero[i] || colZero[j]) {
matrix[i][j] = 0;
}
});
});
}
}
解释
方法:
此题解的思路是首先遍历整个矩阵，记录下所有值为0的元素的行号和列号。利用两个列表分别存储这些行号和列号。在记录行号和列号后，利用集合去重，然后遍历这些唯一的行号，将对应的每一行的所有元素设置为0。接着，遍历这些唯一的列号，将对应的每一列的所有元素设置为0。这样可以确保所有应该被清零的行和列都被正确处理。
时间复杂度:
O(N*M)
空间复杂度:
O(N + M)
代码细节讲解
🦆
在遍历矩阵时，你是如何决定同时记录行号和列号的？这种方法与只记录行号或只记录列号相比有什么优势？
▷🦆
请问为什么在记录行号和列号后，需要使用集合去除重复值而不是直接操作原始列表？
▷🦆
在将行和列设为0的过程中，是否有可能出现对同一行或列重复操作的情况？如果是，这种重复操作有没有办法优化？
▷