LeetCode 面试题 01.08. 零矩阵
目录
题目描述
题意分析
给定
m × n的矩阵，若某个元素为 0，就把它所在的整行和整列全部置零，直接在原矩阵上修改，没有返回值。关键约束藏在「原地修改」四个字里：置零这个动作本身会制造出新的 0，而新产生的 0 不该再触发一轮扩散。所以「读取原始 0 的位置」和「写入 0」这两件事必须在时间上分开，先把全部触发点收集完，再统一落笔。
另一条信号是「行列独立」：某个格子最终是否为 0，只取决于它所在的行里有没有原始 0、它所在的列里有没有原始 0，两者是或的关系。这说明不需要记住每一个 0 的坐标，只需要记住哪些行被标记、哪些列被标记，信息量从 $O(mn)$ 压到 $O(m + n)$。
边界：矩阵至少有一行一列，所以取
matrix[0].length是安全的；全 0 矩阵置零后仍是全 0；不含 0 的矩阵必须原样不动，标记表全假时第二趟不会写入任何值。
解法：哈希表统计状态
核心思路
最朴素的做法是边扫边置零，但它立刻就错：把某行清零后，这一行新出现的 0 会在后续扫描中被当成原始 0，进而把更多列也清掉，最终整个矩阵被污染成全 0。这个失败恰好指出了正确解法的方向——必须区分「原始的 0」和「自己写下的 0」。
退一步，用一个坐标集合记下所有原始 0 的位置，再逐个清行清列，这样答案是对的，但同一行里有多个 0 就会被重复清多次，空间也随 0 的数量增长。观察到「一行只要有一个 0，整行的命运就已经确定」，重复信息可以合并：把集合退化成两张布尔标记表。
于是维护两个状态量：
rows[i]表示第i行在原矩阵中是否出现过 0，cols[j]表示第j列在原矩阵中是否出现过 0。两趟扫描的分工是硬约束——第一趟只读不写，保证rows与cols记录的一定是原始信息；第二趟只写不读判定，matrix[i][j]置零当且仅当rows[i] || cols[j]。这个「先标记后应用」的两趟结构，就是所有「修改会影响后续读取」类矩阵题的通用骨架。
解题步骤
- 取尺寸：
m = matrix.length、n = matrix[0].length。题目保证矩阵非空，因此不必给matrix[0]加判空。- 开两张标记表：
boolean[] rows与boolean[] cols，长度分别是m和n。用布尔而不是计数，是因为「有没有 0」是个是非问题，出现几次不影响结果。- 第一趟只读：遍历每个格子，遇到
matrix[i][j] == 0就同时置rows[i] = true与cols[j] = true。这一趟绝不能写矩阵，否则标记表就被自己制造的 0 污染了。- 第二趟只写：再遍历一次，只要
rows[i] || cols[j]成立就写matrix[i][j] = 0。这里必须用或而不是与——行被标记或列被标记，任一条成立该格就得清零。- 无需返回：题目要求原地修改，函数签名是 void，第二趟结束后矩阵已是答案。
以
matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]走一遍。第一趟扫描只在(1, 1)处遇到 0，于是rows = [false, true, false]、cols = [false, true, false]。第二趟逐格判定：第 0 行里只有j = 1命中cols[1]，得到[1, 0, 1]；第 1 行整行命中rows[1]，得到[0, 0, 0]；第 2 行同第 0 行，得到[1, 0, 1]。最终矩阵为[[1, 0, 1], [0, 0, 0], [1, 0, 1]]。对比一下边扫边清的错误路径：扫到
(1, 1)就把第 1 行第 1 列清零，此时(0, 1)与(2, 1)变成 0；继续扫到(2, 1)时它已经是 0，于是第 2 行又被整行清掉，矩阵被越擦越多。两趟结构正是为了堵死这条路。
代码实现
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, 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)$，两趟遍历各访问每个格子一次，循环体内只有常数次判断与赋值。
- 空间复杂度：$O(m + n)$，两张布尔标记表的长度分别等于行数与列数，与矩阵中 0 的个数无关。
关键点总结
- 当「写操作会改变后续读操作的判定依据」时，就把读和写拆成两趟，这是矩阵、数组类原地修改题的通用解法骨架。
- 判断某格是否置零只需要行标记与列标记的或，不需要记住每个 0 的坐标；识别出这种可合并的冗余信息，是把空间从 $O(mn)$ 降到 $O(m + n)$ 的关键一步。
- 标记用布尔而非计数，因为决策只关心「有没有」；面试中主动说明这一点能体现对状态最小化的敏感度。
- 面试官几乎必定追问常数空间做法：复用第 0 行与第 0 列当标记位，另用两个布尔变量单独记录第 0 行、第 0 列本身是否含 0，第二趟从右下往左上写，最后再处理首行首列。答这道题时最好主动把这条路径讲出来。
- 原地修改类题目要先确认返回值语义——本题返回 void，若习惯性地新建矩阵返回，调用方拿到的仍是未改动的原矩阵。
易错点总结
- 边扫边置零：
[[1, 1, 1], [1, 0, 1], [1, 1, 1]]→ 清完第 1 行第 1 列后新出现的 0 继续触发扩散，最终整个矩阵变成全 0。- 第二趟的条件写成与：
[[1, 0], [1, 1]]→ 只有rows[i] && cols[j]同时成立才清零，结果只有(0, 1)被置 0，第 0 行的(0, 0)和第 1 列的(1, 1)都漏掉。- 只记录行不记录列：
[[1, 0], [1, 1]]→ 得到[[0, 0], [1, 1]]，第 1 列的(1, 1)没有被清掉。- 用
matrix[0].length前先判空却把判空写在取值之后：空矩阵入参时先执行matrix[0]已经越界，判空语句永远轮不到执行。- 两张表共用一个数组：长度取
max(m, n)且行列共用同一份标记，[[0, 1, 1]]→ 第 0 行被标记的同时第 0 列也被误标记，m与n不等时下标含义直接错乱。- 第二趟按行清零时用整行赋值却漏掉列：
[[1, 1], [0, 1]]→ 只把第 1 行填 0 得[[1, 1], [0, 0]]，第 0 列的(0, 0)未清。- 在第一趟里顺手把整行清掉再继续扫：
[[0, 1], [1, 1]]→ 第 0 行清零后(0, 1)变成 0，扫到它时又把第 1 列标记上，得到[[0, 0], [1, 0]]，多清了一列。- 新建结果矩阵并返回：本题签名无返回值，
[[1, 0]]→ 调用方读到的仍是[[1, 0]]，判题直接失败。- 优化到常数空间时忘了先单独记录第 0 行第 0 列：
[[1, 1], [1, 0]]→ 标记位写进第 0 行第 0 列后无法区分它们原本是不是 0，回写阶段把首行首列错误地整体清零。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 73. 矩阵置零 | 中等 | 与本题同题，进阶要求把标记压进第 0 行第 0 列做到常数额外空间 |
| 289. 生命游戏 | 中等 | 同样是「写会污染读」，但状态更多，需用编码位同时保存新旧两态 |
| 48. 旋转图像 | 中等 | 原地修改的另一类型，靠四元素轮换或转置加翻转，不涉及标记表 |
| 面试题 01.07. 旋转矩阵 | 中等 | 与 48 同题，考的是下标映射推导而非扫描顺序 |