 到 O(1) 的原地算法优化)
最近有朋友在准备算法面试，刷到 LeetCode 73 题矩阵置零时卡住了。这道题我前前后后做过三遍，第一遍用额外矩阵复制，第二遍用两个集合标记，第三遍才真正把原地方案吃透。今天把整个思考链路完整梳理一遍，包括三种解法的演进、O(1)空间实现为什么能成立，以及我实际写代码时踩过的坑。
先交代一下题目本身：给定一个 m×n 的矩阵，如果某个元素是 0，就把这个元素所在的整行和整列都置为 0。注意不是只改当前位置，而是所有 0 都要扩散成整行整列。题目要求不要用额外的大空间来完成，最优解是原地处理。
这道题在算法面试里出现频率很高，考察点非常集中：一是你是否清楚“检测”和“修改”必须分离，二是你能不能把空间复杂度从 O(mn) 逐步压缩到 O(1)。下面我从题目本质开始拆。
1. 题目到底在考什么
1.1 先读懂题目：标记与执行必须分离
先看一个最简单的例子。假设矩阵是：
1 2 3 4 0 6 7 8 9输出应该是：
1 0 3 0 0 0 7 0 9原因很简单：元素 0 在第 1 行第 1 列（下标从 0 开始），所以第 1 行全部变 0，第 1 列也全部变 0。矩阵里其他位置保持原样。
这个例子只涉及单个 0，看不出难度。真正的坑出现在多个 0 叠加的场景。比如：
0 2 3 4 0 6 7 8 9第一个 0 在 (0,0)，第二个 0 在 (1,1)。(0,0) 会导致第 0 行和第 0 列清零，(1,1) 会导致第 1 行和第 1 列清零。两者叠加之后，整个矩阵几乎全部变 0。
这里就引出了全题最关键的一个原则：置零是一次性的扩散，不是涟漪式的连锁反应。某个位置因为“行里有 0”或者“列里有 0”而变成 0 之后，这个新产生的 0 不应该再继续去引发它自己所在行和列的二次清零。
用一个生活类比来说：这就像广播通知，你得先收集完所有需要通知的人员名单，然后统一广播。如果在广播过程中不断把新听到消息的人继续加入名单、继续广播，消息就会越传越多，最终失去控制。
所以正确思路一定是：先扫描，记录所有需要被清零的行和列；再统一执行清零。检测阶段和执行阶段必须分开，这是整道题的地基。
1.2 空间复杂度是真正的考点
这道题的时间复杂度几乎没有讨论空间，因为不管用什么方法，你都得把矩阵里的每个格子至少看一遍，所以时间必然是 O(mn)。真正的区分度在空间复杂度，面试官几乎必然会沿着下面这条线引导你：
第一档空间 O(mn)，复制一份矩阵当“判决依据”。代码简单，但空间开销大。
第二档空间 O(m+n)，只记录有 0 的行和列。这一步已经足够日常工程使用。
第三档空间 O(1)，把标记信息直接存回矩阵自己的第一行和第一列。这也是这道题最有魅力的一步。
面试官通常不指望你上来就写 O(1) 版本，而是看你能不能从最容易想到的方案开始，一层一层优化下去，并且解释清楚每一步为什么正确。很多人能写出前两种，但到 O(1) 那一步就开始乱了，原因就是对“标记与执行必须分离”这个底层逻辑理解得不够透。
2. 解法演进：从“会做”到“最优解”
2.1 解法一：复制矩阵，最直观但不推荐
最容易想到的方案是复制一份矩阵，然后遍历原矩阵。只要原矩阵某个位置是 0，就把复制矩阵的对应整行整列全部改成 0。最后把复制矩阵的结果写回原矩阵。
Python 实现大概长这样：
def setZeroes(matrix): m, n = len(matrix), len(matrix[0]) copy = [row[:] for row in matrix] for i in range(m): for j in range(n): if copy[i][j] == 0: for k in range(m): matrix[k][j] = 0 for k in range(n): matrix[i][k] = 0这个方案能正确解决问题，因为它把“检测”和“执行”完全分开了：检测时看的是复制矩阵，执行时改的是原矩阵，互不干扰。
但它的缺点也明显：空间复杂度 O(mn)，一个 n 行 m 列的矩阵就要额外开一份同样大小的内存。如果矩阵是 1000×1000，你得多存 100 万个整数。刷题时这么写没问题，但面试时如果就此打住，空间优化那部分分就丢了。我认为这个版本存在的价值只是作为讨论的起点，帮助确认你已经理解了题目的基本规则。
2.2 解法二：两个标记集合，空间 O(m+n)
仔细想一下，最终哪些位置会变成 0，完全由两个独立的信息决定：这一行里是否存在 0，这一列里是否存在 0。某个位置 (i,j) 会被清零，当且仅当第 i 行有 0 或者第 j 列有 0。
所以根本不需要记录矩阵里每一个 0 的位置，只需要记录两件事：哪些行有 0，哪些列有 0。用两个布尔数组或者两个集合存就行。
def setZeroes(matrix): m, n = len(matrix), len(matrix[0]) row_flag = [False] * m col_flag = [False] * n for i in range(m): for j in range(n): if matrix[i][j] == 0: row_flag[i] = True col_flag[j] = True for i in range(m): for j in range(n): if row_flag[i] or col_flag[j]: matrix[i][j] = 0这个方案空间复杂度 O(m+n)，逻辑非常清晰。第一遍扫描只负责收集信息，第二遍扫描只负责修改数据。把原本 O(mn) 的空间直接降到了 O(m+n)，这是一个很大的跨越。
而且在很多真实工程场景下，这个方案其实比 O(1) 版本更实用。比如矩阵轮廓信息、图像数据里的零值标记，开两个长度分别为行数和列数的布尔数组，成本很低，代码可读性也高。如果面试官没有特殊要求，果断写这个版本是稳的。
2.3 解法三：把第一行和第一列当成标记板，空间 O(1)
空间还能不能继续压缩？O(m+n) 已经跟矩阵的规模线性相关了，想要常数空间，就只能从“把信息塞回原矩阵”这条路上想办法。
注意一个事实：矩阵第一行有 n 个格子，第一列有 m 个格子，这些格子本来就是矩阵的一部分。我们可以把“第 j 列是否需要清零”这个状态，存到 matrix[0][j] 上；把“第 i 行是否需要清零”这个状态，存到 matrix[i][0] 上。这样就用矩阵自己的边界空间完成了标记，不需要额外申请任何数组。
但这里有一个非常容易忽略的冲突点：matrix[0][0] 这个格子同时处于第一行和第一列。如果它被用来代表“第 0 列是否有 0”，那你就不再有地方存放“第 0 行是否有 0”的状态；反过来也一样。所以必须用两个额外的布尔变量，先把第一行、第一列本身的状态单独记下来，再把剩余的行列信息写进边界。
整个过程拆成四步：
- 记录第一行是否存在 0，记录第一列是否存在 0。
- 从 (1,1) 开始遍历矩阵内部，遇到 0 就更新边界标记：matrix[i][0] = 0，matrix[0][j] = 0。
- 再次从 (1,1) 开始遍历，根据边界标记把内部元素清零：如果 matrix[i][0] == 0 或者 matrix[0][j] == 0，就把 matrix[i][j] 置为 0。
- 最后根据第一步记录的两个变量，单独处理第一行和第一列。
下面这个表格可以帮你快速对比三种解法的定位：
| 解法 | 空间复杂度 | 核心思路 | 适用场景 |
|---|---|---|---|
| 复制矩阵 | O(mn) | 空间换简单 | 只求快速通过 |
| 两个标记数组 | O(m+n) | 行与列独立记录 | 工程中最常用 |
| 第一行第一列标记 | O(1) | 原矩阵边界当白板 | 面试进阶考察点 |
3. 核心实现细节：原地置零的完整流程
3.1 完整可运行代码
先给 Python 版本，这是我在 LeetCode 上常用的写法：
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: m, n = len(matrix), len(matrix[0]) first_row_zero = False first_col_zero = False # 第一步：单独记录第一行和第一列本身是否有0 for j in range(n): if matrix[0][j] == 0: first_row_zero = True break for i in range(m): if matrix[i][0] == 0: first_col_zero = True break # 第二步：用第一行和第一列作为标记板 for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0: matrix[i][0] = 0 matrix[0][j] = 0 # 第三步：根据标记清零内部元素 for i in range(1, m): for j in range(1, n): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 # 第四步：处理第一行和第一列 if first_row_zero: for j in range(n): matrix[0][j] = 0 if first_col_zero: for i in range(m): matrix[i][0] = 0C++ 版本也一并给出，方便在不同语言习惯下互相对照：
class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); bool firstRowZero = false, firstColZero = false; for (int j = 0; j < n; ++j) { if (matrix[0][j] == 0) { firstRowZero = true; break; } } for (int i = 0; i < m; ++i) { if (matrix[i][0] == 0) { firstColZero = true; break; } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (firstRowZero) { for (int j = 0; j < n; ++j) { matrix[0][j] = 0; } } if (firstColZero) { for (int i = 0; i < m; ++i) { matrix[i][0] = 0; } } } };代码看起来不长，但每一步都有明确目的。第二步扫描范围是 (1,1) 到 (m-1,n-1)，刻意避开第一行和第一列；第三步同样避开边界。这个“避开”不是可有可无的细节，而是整个方案成立的关键。
3.2 为什么标记信息不会在置零过程中被破坏
很多人第一次看到这个解法时都会有疑问：边界上的 matrix[i][0] 和 matrix[0][j] 也是矩阵的一部分，等会儿执行清零时，这些标记位置不也会被清零吗？标记被清掉了，第三步的信息从哪来？
答案在于执行顺序。
仔细看代码：第二步写标记的时候，只遍历内部区域，不碰第一行和第一列。第三步读标记清零的时候，读的是 matrix[i][0] 和 matrix[0][j]，改的是 matrix[i][j]，也没有去动边界。只有当前三步做完之后，第四步才会去处理第一行和第一列本身。到那时候，内部元素该清的已经清完了，边界被改成什么样都无所谓了。
我建议你手动模拟一个例子来加深理解。用这个矩阵：
1 2 3 4 0 6 7 8 9先记录第一行没有 0，第一列也没有 0，所以 firstRowZero = false，firstColZero = false。
第二步发现 (1,1) 位置是 0，于是把 matrix[1][0] 改成 0，把 matrix[0][1] 改成 0。矩阵变成：
1 0 3 0 0 6 7 8 9第三步遍历内部元素，凡是 matrix[i][0] == 0 或者 matrix[0][j] == 0 就清零。第 1 行的行标记已经变成 0，所以整第 1 行被清零；第 1 列的列标记也已经变成 0，所以第 1 列被清零。
最终：
1 0 3 0 0 0 7 0 9完美匹配预期结果。
再试一个第一行本身带 0 的例子：
0 2 3 4 0 6 7 8 9第一步记录 firstRowZero = true，firstColZero = true，因为 (0,0) 本身是 0。
第二步从 (1,1) 开始扫，发现 (1,1) 是 0，把 matrix[1][0] 和 matrix[0][1] 都改成 0。此时矩阵：
0 0 3 0 0 6 7 8 9第三步清零内部后，矩阵变成：
0 0 3 0 0 0 7 0 9第四步因为 firstRowZero 为 true，第一行整行清零；firstColZero 为 true，第一列整列清零。最终：
0 0 0 0 0 0 0 0 0结果对不对？左上角 (0,0) 本身是 0，它会让第一行和第一列全部清零；内部 (1,1) 是 0，会让第 1 行和第 1 列全部清零。四个角落和两条中间轴全部覆盖，确实整个矩阵都该是 0。逻辑自洽。
3.3 边界情况处理要点
LeetCode 官方的约束通常保证了矩阵至少一行一列，但写代码时还是要有防御意识。
如果 m 或 n 可能为 0，len(matrix[0]) 会直接越界。可以在函数开头加一句：
if not matrix or not matrix[0]: return单行矩阵的情况，比如 [[1,0,1]]。第一步扫描第一行时，firstRowZero 会被置为 true。第二步和第三步的循环因为 m 等于 1，range(1, m) 为空，自然跳过。最后第四步把第一行整行清零，结果是 [[0,0,0]]。这符合题意。
单列矩阵的情况同理。比如：
1 0 1firstColZero 为 true，最后整列清零。
全非 0 矩阵的情况最省心，所有标记都不触发，矩阵原样返回。全 0 矩阵则所有标记都触发，结果整个矩阵全 0，也正确。
4. 常见问题与排查实录
4.1 高频错误盘点
我把实际写代码过程中最容易出的四个错误整理成一张表，每条都是真实踩过的坑：
| 错误类型 | 错误现象 | 根因分析 | 解决方案 |
|---|---|---|---|
| 边扫边改 | 矩阵里的 0 越滚越多，几乎全变 0 | 检测和修改混在一起，新产生的 0 参与后续判断 | 先收集标记，再统一执行 |
| 忽略 matrix[0][0] 冲突 | 首行或首列被错误清空 | matrix[0][0] 同时代表行标记和列标记状态 | 用两个额外布尔变量单独记录 |
| 清零时从 (0,0) 开始遍历 | 标记被提前清掉，后续列全部失效 | 内部清零阶段碰了第一行第一列 | 第二步和第三步都从 (1,1) 开始 |
| 下标写反 | 某行被清成了列，某列被清成了行 | matrix[i][0] 和 matrix[0][j] 混用 | 写完后逐行检查索引 i/j 的位置 |
其中“边扫边改”是最初级的错误。比如你在遍历时遇到一个 0，立刻把整行整列清零，但后面还没遍历到的位置已经被你改成了 0，程序会以为那里原本就是 0，于是继续清零它的整行整列。一轮扩散下来，结果就是大面积误伤。
“忽略 matrix[0][0] 冲突”也很隐蔽。假如第一行存在 0 但第一列不存在 0，如果你只用 matrix[0][0] 来进行边界判断，就会把第一列也错误清空。因为 matrix[0][0] 既记录了行的信息，也参与了列的信息推导。
“清零时从 (0,0) 开始遍历”是我自己当初犯过的错。我当时写第三步时很顺手地用了双重 for 从 0 开始，结果第一步刚把 matrix[0][j] 标记写进去，第三步一上去就把这些标记清零了。后面的元素再也读不到列信息，结果大面积漏清。
4.2 自测用例与排查技巧
提交代码之前，我建议先跑下面这一组用例，覆盖各种典型场景：
用例1： [[1,1,1], [1,0,1], [1,1,1]] 预期： [[1,0,1], [0,0,0], [1,0,1]] 用例2： [[0,1,2,0], [3,4,5,2], [1,3,1,5]] 预期： [[0,0,0,0], [0,4,5,0], [0,3,1,0]] 用例3： [[0,1]] 预期： [[0,0]] 用例4： [[1], [1], [0]] 预期： [[0], [0], [0]]用例 2 比较典型，它同时包含首尾两个 0，会触发第一行和最后一列的清零，内部还有独立的 0 触发中间列，能很好地检验边界标记和内部标记是否冲突。
排查时我有一个习惯：在标记阶段结束后和执行阶段结束后分别打印一次矩阵。第一次打印可以看到第一行和第一列是否被正确改写成了“标记集合”，第二次打印可以确认清零是否只影响了该影响的行列。这一步能快速定位绝大多数索引错误。
4.3 面试追问与扩展思考
如果你把 O(1) 解法写出来了，面试官很可能会继续追问或者换场景考察。常见的问题方向有几个：
第一个方向是“为什么 O(1) 空间是可行的”。本质原因是，行信息有 m 个、列信息有 n 个，这些信息恰好可以映射到矩阵边界已有的 m+n 个格子上，不需要额外分配内存。
第二个方向是“如果矩阵的内存特别珍贵，不想破坏原数据怎么办”。这时可以讨论位图或者额外开一个长度非常小的标记数组。但要注意，如果允许覆盖边界，原地方案就是最优的。
第三个方向是“如果矩阵很大但是 0 很少，空间上有没有更灵活的做法”。这时候用两个稀疏的哈希集合可能更合适，因为空间只跟 0 的个数相关，而不是跟矩阵尺寸相关。虽然理论上空间复杂度还是 O(m+n) 的上界，但实际内存占用会小很多。
第四个方向是相关题目的迁移。比如生命游戏这类题目，同样要求在原数组上用标记位保存多个状态，思路和这题一脉相承。做过这题之后再做生命游戏，你会发现“把信息存回数组自身”这个套路是相通的。
最后再说一个我个人的刷题体会。这道题我第一次做的时候，五分钟就写完了复制矩阵版本，当时觉得自己会了。后来在一次模拟面试里被要求优化到 O(1)，我才意识到自己只是“会跑通”，不是“会想透”。真正把第一行第一列标记法理解清楚之后，最大的收获不是背下了这题的代码，而是建立了一种空间优化直觉：当题目不允许你开额外空间时，先看看数据本身有没有没被利用起来的位置，再想想操作顺序怎么设计才能保证标记不被提前销毁。带着这个思路去刷后续的原地修改类题目，你会顺手很多。
