Hot100 73 | 矩阵置零：标记法与原地优化

系列导航：LeetCode Hot100 刷题导航（系列导航） · 上一篇：Hot100 560 | 和为 K 的子数组：前缀和加哈希表

这题是进入 矩阵 专题的第一题。它会让你第一次真正感受到：二维数组题很多时候不能“看见 0 就立刻改”，而是要先设计一个安全的标记策略。

专栏导读

这题很适合训练一种特别重要的矩阵思维：

判断和修改最好分开做

因为在二维数组里，如果你边扫边改，刚改出来的新值很可能会污染后面的判断。

这篇会重点讲清楚下面几件事：

题目到底要你改什么
为什么不能一边遍历一边直接置零
行集合和列集合各自记录什么
为什么必须分成两轮处理
为什么第一行和第一列还能拿来做原地标记

1. 题目到底在说什么

题目给你一个矩阵 matrix。

规则是：

只要某个位置原本是 0
那它所在的整行和整列，最后都要变成 0

例如：

1
2
3

[[1,1,1],
 [1,0,1],
 [1,1,1]]

处理后应该变成：

1
2
3

[[1,0,1],
 [0,0,0],
 [1,0,1]]

2. 这题最容易误解的地方

很多人第一次写这题，最自然的想法是：

扫到一个 0
就立刻把这一整行和这一整列改成 0

这看起来很顺，但其实非常危险。

为什么？

因为你刚改出来的新 0，会被后面的遍历当成“原本就有的 0”，从而继续扩散，导致本来不该清零的地方也被清掉。

所以这题最关键的不是“怎么改”，而是：

怎么先记住哪些行和列该改

3. 用一个最小例子说明为什么不能边扫边改

例如矩阵：

1
2
3

[[1,1,1],
 [1,0,1],
 [1,1,1]]

如果你扫描到中间那个 0 时，立刻把整行整列清零，就会先变成：

1
2
3

[[1,0,1],
 [0,0,0],
 [1,0,1]]

这一步本身没错。

但如果你后面继续遍历时，又把这些“新改出来的 0”当成原始 0 来处理，就会继续扩散，最后整个矩阵可能都会被清零。

所以真正稳的思路一定是：

第一轮只判断，不修改
第二轮再统一修改

4. 先把题目翻译成人话

如果把这题翻译成最直白的话，其实就是：

先把所有“需要清零的行号”和“需要清零的列号”记下来
然后再重新扫一遍矩阵
只要某个位置处于这些行或列里，就把它改成 0

这就是这题最自然的第一层解法。

5. 方法一：用两个集合做标记

5.1 为什么先讲这个方法

虽然这题还能继续优化到原地标记，但对刷题新手来说，最稳的顺序还是：

先写出最不容易错、最容易理解的版本
再理解如何优化空间

所以这里最推荐你先掌握的是：

一个集合记录要清零的行
一个集合记录要清零的列

5.2 Python Tutor 版代码

def set_zeroes(matrix):
    rows = set()
    cols = set()

    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 0:
                rows.add(i)
                cols.add(j)

    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if i in rows or j in cols:
                matrix[i][j] = 0

matrix = [[1,1,1],[1,0,1],[1,1,1]]
set_zeroes(matrix)
print(matrix)

5.3 LeetCode 可提交版代码

class Solution:
    def setZeroes(self, matrix):
        rows = set()
        cols = set()

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i in rows or j in cols:
                    matrix[i][j] = 0

6. 每一行代码在做什么

先看：

1 2	rows = set() cols = set()

这里两个集合的职责非常明确：

rows：记录哪些行最后要全部变成 0
cols：记录哪些列最后要全部变成 0

6.1 第一轮遍历：只做记录

for i in range(len(matrix)):
    for j in range(len(matrix[0])):
        if matrix[i][j] == 0:
            rows.add(i)
            cols.add(j)

这段代码的核心任务只有一个：

找出原始矩阵里哪些位置本来就是 0

注意，这一轮绝对不修改矩阵。

一旦遇到 0，就说明：

这一整行以后都要清零
这一整列以后也都要清零

于是：

1 2	rows.add(i) cols.add(j)

这里为什么用集合？

因为：

行号和列号只要记一次就够了
重复加入集合也不会出问题

6.2 第二轮遍历：统一修改

for i in range(len(matrix)):
    for j in range(len(matrix[0])):
        if i in rows or j in cols:
            matrix[i][j] = 0

这轮才是真正开始动手改矩阵。

这里的判断：

1	if i in rows or j in cols:

意思是：

只要当前位置所在行需要清零
或者所在列需要清零
那当前位置就必须变成 0

这里的 or 特别关键。

因为题目要求是：

行或列命中都要清零

不是行和列都命中才清零。

7. 用示例手动走一遍

示例：

1
2
3

[[1,1,1],
 [1,0,1],
 [1,1,1]]

第一轮：只记录行列

遍历时会发现：

第 1 行第 1 列有一个 0

于是：

rows = {1}
cols = {1}

这时候矩阵本身还保持原样。

第二轮：根据记录统一清零

现在重新扫矩阵。

只要某个位置满足：

行号是 1
或列号是 1

它就会变成 0。

所以结果变成：

1
2
3

[[1,0,1],
 [0,0,0],
 [1,0,1]]

这就是正确答案。

8. 为什么这方法很稳

因为它把题目拆成了非常清晰的两步：

第一步：找信息

哪些行要清零
哪些列要清零

第二步：用信息改矩阵

这样就不会让“新改出来的 0”反过来影响判断。

所以这版虽然不是空间最优，但对初学者极其友好。

9. 还能怎么优化：用第一行和第一列做标记

如果你准备继续提高，这题还有一个更进阶的思路：

不额外开两个集合
直接把第一行和第一列本身当成标记区

例如：

如果第 i 行需要清零，就把 matrix[i][0] 置为 0
如果第 j 列需要清零，就把 matrix[0][j] 置为 0

这样可以把额外空间进一步压到更低。

不过这版会复杂不少，因为：

第一行和第一列既要当真实数据
又要当标记区
所以通常还要额外记录“第一行本来要不要清零”“第一列本来要不要清零”

如果你现在还在矩阵题入门阶段，我更建议你先把集合标记法彻底掌握，因为它最不容易写错。

10. 这题顺手学到的 Python 语法

10.1 `set()`

用来记录唯一的行号和列号。

10.2 二维数组遍历

1 2	for i in range(len(matrix)): for j in range(len(matrix[0])):

这是矩阵题里最基础的双层循环写法。

10.3 `in`

1	if i in rows or j in cols:

表示判断当前行号或列号是否在标记集合里。

11. 这题最容易犯的错

11.1 一边遍历一边直接改矩阵

这会让后面的判断被“新产生的 0”污染。

11.2 只记录行，不记录列

或者反过来只记录列，不记录行，都不完整。

11.3 没理解为什么必须分两轮

这题最关键的就是：

第一轮只判断
第二轮再修改

11.4 `or` 写成 `and`

只要行或列命中就要清零，所以必须是 or。

12. 一句话复盘

这题的本质不是“看到 0 就立刻扩散清零”，而是先把该清零的行列标记下来，再统一修改矩阵。

13. 下一步怎么学

如果你继续往后刷矩阵专题，后面就可以开始练更有空间感和方向感的矩阵题，比如螺旋矩阵、旋转图像之类。