LeetCode hot 100 每日一题(13)——73. 矩阵置零
这是一道难度为中等的题目，让我们来看看题目描述：
给定一个
_m_ x _n_的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
提示：
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200- - 2 31 2^{31} 231 <= matrix[i][j] <= 2 31 2^{31} 231 - 1
题解
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length; // 获取矩阵的行数
int n = matrix[0].length; // 获取矩阵的列数
boolean[] row = new boolean[m]; // 记录需要置零的行
boolean[] col = new boolean[n]; // 记录需要置零的列
// 第一遍遍历矩阵，标记所有含有 0 的行和列
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] == 0){
row[i] = true; // 标记该行需要置零
col[j] = true; // 标记该列需要置零
}
}
}
// 第二遍遍历矩阵，根据标记的行和列将相应元素置零
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(row[i] || col[j]){ // 如果当前行或列被标记为需要置零
matrix[i][j] = 0; // 置零操作
}
}
}
}
}
解题思路
1. 题目分析
给定一个 m × n 的矩阵，如果某个元素为 0，则需要将它所在的整行和整列的所有元素都设为 0。要求在原矩阵上直接修改，不能使用额外的矩阵存储修改后的数据。
2. 解法思路
-
第一步：标记所有需要置零的行和列
-
用两个数组
row[]和col[]分别记录哪些行和列需要置零。 -
遍历矩阵，如果遇到
matrix[i][j] == 0，就将row[i]和col[j]标记为true，表示该行或该列需要全部置零。
-
-
第二步：遍历矩阵，根据标记进行置零
- 再次遍历矩阵，如果
row[i]为true或col[j]为true，说明该位置matrix[i][j]需要置零。
- 再次遍历矩阵，如果
3. 复杂度分析
-
时间复杂度：O(m × n)
- 需要两次遍历整个矩阵，时间复杂度为
O(m × n)，符合题目要求。
- 需要两次遍历整个矩阵，时间复杂度为
-
空间复杂度：O(m + n)
- 额外使用了
row[]和col[]两个数组，空间复杂度为O(m + n)。
- 额外使用了
4. 进阶优化
如果希望减少额外空间使用，可以利用矩阵的第一行和第一列来存储这些标记，而不使用额外的 row[] 和 col[] 数组，进而将空间复杂度优化为 O(1)。
问题与解答
[NOTE] 问题1：
if(row[i] || col[j])这一句我有一点不懂，为什么要么行或列被标记，就会被置0呢？
解答：
这个if(row[i] || col[j])条件的作用是：如果当前元素所在的行i或列j需要置零，则将该元素matrix[i][j]置为0。
为什么这样判断？
想象一下矩阵的置零规则：
- 如果一个元素
matrix[i][j] == 0，那么它所在的整行 和 整列 都要变成0。- 在第一遍遍历矩阵时，我们用
row[i]记录第i行是否需要全部变 0，用col[j]记录第j列是否需要全部变 0。- 因此，在第二遍遍历时：
- 如果
row[i] == true，说明该行有一个元素原本是0，所以整行要变0，当前元素matrix[i][j]也必须变0。- 如果
col[j] == true，说明该列有一个元素原本是0，所以整列要变0，当前元素matrix[i][j]也必须变0。- 只要满足任意一个条件 (
row[i]或col[j])，当前元素matrix[i][j]必须变成0。
举例分析
示例 1
输入矩阵：
[ [1, 1, 1], [1, 0, 1], [1, 1, 1] ]第一遍标记
row[]和col[]row = [false, true, false] // 第 1 行（索引 1）需要置零 col = [false, true, false] // 第 1 列（索引 1）需要置零第二遍遍历并置零（应用
if(row[i] || col[j])）[ [1, 0, 1], // 因为 col[1] = true，第二列所有元素变 0 [0, 0, 0], // 因为 row[1] = true，整行变 0 [1, 0, 1] // 因为 col[1] = true，第二列所有元素变 0 ]总结
row[i]记录行是否要变 0，col[j]记录列是否要变 0。if(row[i] || col[j])的含义是：
- 如果这一行之前有
0，则当前行的所有元素都要变0。- 如果这一列之前有
0，则当前列的所有元素都要变0。- 如果当前行或列任意一个需要变 0，那么
matrix[i][j]也必须变 0。- 这样就符合题目的要求，用 两次遍历 实现 原地置零。