LeetCode 面试题 01.08. 零矩阵
题目描述
题意分析
原矩阵中只要有一个位置为 0，就把它所在的整行、整列清零，并直接修改输入矩阵。判断依据始终是修改前的零；操作新产生的零不能继续触发其他行列清零。
解法：先记录原始零的行列再统一写回
核心思路
[!blue]
如果扫描到零就立即清整行整列，后续扫描会把刚写出的零也当作原始零，导致清零范围不断扩大。因此先记录需要修改的范围，等判断全部完成后再统一写入。
用
rows[i]表示原矩阵第i行是否出现过零，用cols[j]表示第j列是否出现过零。第一趟只读矩阵，遇到零就同时将对应行、列标记为true；同一行列有多个零也只需保留一个布尔标记。第二趟处理位置
(i, j)时，若rows[i] || cols[j]为真，就说明它与某个原始零同行或同列，必须清零；若两者都为假，则没有任何原始零要求修改它，应保留原值。这个条件恰好覆盖全部目标位置，既不会漏清，也不会额外传播。第二趟只读取已经固定的标记，因此写入顺序不再影响判断。单行或单列矩阵也使用同一规则；若没有原始零，全部标记为假，矩阵自然保持不变。
解题步骤
- 创建 m 行和 n 列的标记。
- 遍历原矩阵，遇到零同时标记所在行列。
- 再次遍历，rows[i] 或 cols[j] 成立即置零。
代码实现
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[] rows = new boolean[m];
boolean[] cols = new boolean[n];
// 第一趟只读：记录原始 0 所在的行与列。
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
rows[i] = true;
cols[j] = true;
}
}
}
// 第二趟只写：行或列被标记就置零。
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (rows[i] || cols[j]) {
matrix[i][j] = 0;
}
}
}
}
}
func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
rows := make([]bool, m)
cols := make([]bool, n)
// 第一趟只读：记录原始 0 所在的行与列。
for i, row := range matrix {
for j, v := range row {
if v == 0 {
rows[i] = true
cols[j] = true
}
}
}
// 第二趟只写：行或列被标记就置零。
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if rows[i] || cols[j] {
matrix[i][j] = 0
}
}
}
}
复杂度分析
- 时间复杂度：$O(mn)$，
m、n为行列数，两趟都只扫描每个位置一次。- 空间复杂度：$O(m+n)$，只保存行、列标记，结果直接写回原矩阵。
关键点总结
[!green]
读原始状态与写最终状态分开，避免新生成的零污染后续判断。
易错点总结
[!yellow]
- 第二趟使用或，写成与只会清行列交点。
- 不要在第一趟清整行或整列。
- 需要原地改输入，单独新建矩阵但不回写无法完成接口要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 289. 生命游戏 | 中等 | 同样需要区分旧状态和本轮更新结果，原题还可通过原地状态编码保存两代信息。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！