空间原地标记法，LeetCode 73 面试必会)
LeetCode 73矩阵置零是我刷题过程中印象很深的一道题——它难吗真不难题目三句话就能说清但它几乎是冲着“面试高频”四个字量身定做的在“原地算法 O(1)空间优化”的封锁下隐藏的坑一个接一个。很多人看完题目觉得“不就遍历一遍把行列记下来嘛”结果一提交要么多开了数组被面试官揪住不放要么直接把不该变 0 的元素也牵连着改了。这篇文章我就从暴力解法到最优的原地标记法把整条思考链路、Python 实现细节和面试追问逻辑一次讲清楚保证你看完再遇到这道题可以直接默写。1. 面试现场的第一印象这题怎么一眼看穿考点1.1 题目回顾与输入输出约束题目要求一句话描述给定一个m x n的矩阵如果某个元素是0就把这个元素所在的整行和整列都置为0。注意几个关键词就地修改in-place、不能返回新矩阵、空间复杂度尽量控制在 O(1)。举个例子输入[ [1, 1, 1], [1, 0, 1], [1, 1, 1] ]原矩阵中(1, 1)位置是 0那么第 1 行和第 1 列全部变成 0输出[ [1, 0, 1], [0, 0, 0], [1, 0, 1] ]很多人看到这里会觉得简单啊先遍历一遍碰到 0 就把行和列标出来第二遍再统一改。但面试官真正看的是你有没有意识到“直接改”会造成连锁污染以及你能否在空间受限的情况下依然给出整洁、不 bug 的方案。1.2 高频背后的三个考察维度这道题被列为面试高频不是没有原因的我把它拆成三个考察维度二维数组的基本功能否熟练处理行列下标能否在双循环里理清“标记”和“修改”两个阶段。空间优化的审美从 O(mn) 到 O(mn) 再到 O(1)每一步优化都体现你对“数据本身可不可以复用”的理解。边界条件的严谨性第一行、第一列既是数据又是标记区处理不好就直接 GG。在面试里多数人卡在第三点。我自己第一次独立写这个最优解时也是在一个 3x3 的用例上栽了跟头输出结果比预期多了一整行 0。这种挫折记忆特别深所以我想把它写透。1.3 两个典型错误解法为什么必挂先聊聊两个“看起来对、实际拉胯”的解法。第一种是复制矩阵法new_matrix [row[:] for row in matrix]然后遍历新矩阵里的 0去修改原矩阵。这个方法能 AC空间复杂度 O(mn)但面试官只要追问一句“能不能原地做”就暴露了。它的问题不是逻辑错而是完全没有优化意识在面试评级里属于“刚及格”。第二种是边遍历边置零遍历到matrix[i][j] 0立刻把第 i 行、第 j 列全改 0。这个解法的问题非常隐蔽——当你把一行改成 0 之后这个新出现的 0 会被后续循环当成“原始 0”从而继续清空其他行列最后整个矩阵全被污染成 0。比如[ [0, 1], [1, 1] ]遍历到(0, 0)时把第 0 行和第 0 列置 0矩阵变成[ [0, 0], [0, 1] ]接着遍历到(0, 1)发现它是 0于是又把第 1 列清掉矩阵变成[ [0, 0], [0, 0] ]正确答案其实应该是[ [0, 0], [0, 1] ]这种“边改边遍历”的连锁反应是绝大多数新手第一次写这道题挂掉的原因。理解了这两个错误最优解的思路也就呼之欲出了你得先标记再统一修改不能边标记边修改。2. 最优解的核心洞察让矩阵自己记住“哪些行哪些列要清零”2.1 从暴力到 O(mn)标记数组思路先把最简单可用的正确解法写出来。我们可以开两个一维数组row_flag [False] * m记录哪几行需要清零col_flag [False] * n记录哪几列需要清零第一遍遍历原始矩阵如果matrix[i][j] 0就设置row_flag[i] True和col_flag[j] True。第二遍遍历只要row_flag[i] or col_flag[j]为真就把matrix[i][j]置为 0。这个解法的时间复杂度 O(mn)空间复杂度 O(mn)。放在笔试里已经能满分开销也不算大但面试官通常不会就此收手他会追问“能不能把空间压到 O(1)”2.2 关键一步把标记数组合并进矩阵本身O(1) 空间优化的核心洞察很朴素既然第一行和第一列早晚要被处理那干脆利用它们来记录标记信息。具体来说用matrix[i][0]记录第 i 行是否需要清零用matrix[0][j]记录第 j 列是否需要清零这样我们不需要额外的row_flag和col_flag矩阵自己就把标记记完了。但你马上会发现一个致命问题matrix[0][0]既是第 0 行的标记位又是第 0 列的标记位。它一个格子被两个角色共用这会造成信息混乱如果matrix[0][0] 0我到底该理解为“第一行要清零”还是“第一列要清零”这就是整个题目最精妙也最容易被忽略的地方。2.3 最大的坑第一行和第一列是“标记板”不是“数据”我的处理办法是在第一遍遍历之前先用两个布尔变量把第一行和第一列的真实情况保存下来。row0_has_zero第一行里是否存在 0col0_has_zero第一列里是否存在 0然后在后续所有标记和回写过程中我们都只把第一行和第一列当作标记区对待不再把它们当作普通数据去判断。正常的行和列从下标 1 开始处理。这样做的好处是第一行和第一列的原始信息已经提取到两个布尔变量里之后即使第一行被改得面目全非也不会影响最终的恢复逻辑。2.4 为什么非要额外两个布尔变量有同学可能会问能不能省掉这两个布尔变量可以但要付出代价。有一种常见优化是用matrix[0][0]单独表示“第一行是否有 0”再用一个额外变量col0表示“第一列是否有 0”。这样空间上更省只多一个布尔量。代价是代码可读性下降而且你要非常小心地处理标记和回写的顺序否则很容易因为matrix[0][0]被提前修改而出错。我的建议是面试的时候不要强行省这个变量。两个布尔量也是 O(1) 空间从大 O 角度完全一样但代码的清晰度和可维护性高一个台阶。面试官不会因为你多用一个布尔变量扣分他只会因为你写了个他自己都看不懂的炫技解法而皱眉。3. Python 实现与小样例全流程推演3.1 完整代码含边界防御直接上完整代码本地能跑LeetCode 也能直接提交from typing import List class Solution: def setZeroes(self, matrix: List[List[int]]) - None: Do not return anything, modify matrix in-place instead. if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) # 提前记录第一行、第一列是否存在 0 row0_has_zero False col0_has_zero False for j in range(n): if matrix[0][j] 0: row0_has_zero True break for i in range(m): if matrix[i][0] 0: col0_has_zero True break # 第一遍用第一行和第一列充当标记板 # 注意遍历范围只覆盖 [1..m-1] 和 [1..n-1] 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 row0_has_zero: for j in range(n): matrix[0][j] 0 if col0_has_zero: for i in range(m): matrix[i][0] 0这段代码我加了两行防御if not matrix or not matrix[0]: return。LeetCode 的测试用例不会给你空矩阵但本地调试时万一用到不至于直接 IndexError。3.2 示例推演3×3 典型场景拿前面的经典用例走一遍matrix [ [1, 1, 1], [1, 0, 1], [1, 1, 1] ]第一步检查第一行有没有 0没有row0_has_zero False。检查第一列有没有 0也没有col0_has_zero False。第二步从(1, 1)开始遍历内部区域。发现matrix[1][1] 0于是设置matrix[1][0] 0 matrix[0][1] 0此时矩阵变成[ [1, 0, 1], [0, 0, 1], [1, 1, 1] ]注意这里matrix[0][1]被改成了 0但因为它标记区不影响我们后续判断内部区域。matrix[0][0]没被动matrix[1][0]虽然是第一列的值但它是第 1 行的标记。第三步回写内部区域。遍历所有(i, j)第 1 行matrix[1][0] 0所以(1, 1)和(1, 2)都置 0。第 2 行matrix[2][0] 1不是 0但matrix[0][1] 0所以第 1 列对应的(2, 1)置 0(2, 2)因为两个标记都不为 0保持不变。此时矩阵[ [1, 0, 1], [0, 0, 0], [1, 0, 1] ]第四步根据row0_has_zero和col0_has_zero回写第一行第一列这两个布尔变量都是 False于是不动。最终结果完全正确。3.3 极端情况验证单行单列与全零矩阵面试时一定要主动验证边界情况这比闷头写代码更能加分。我列几个常用用例输入正确输出代码表现[[1, 0, 3]][[0, 0, 0]]内部区域循环跳过回写第一行全 0[[1], [0], [3]][[0], [0], [0]]内部区域循环跳过回写第一列全 0[[0, 1], [1, 1]][[0, 0], [0, 1]]边界变量正确记录第一行第一列有 0[[1, 2], [3, 4]]原矩阵不变无标记回写判定全部为 False[[0, 0], [0, 0]]全 0标记区和布尔变量全为真其中单行[[1, 0, 3]]是很容易漏掉的边界因为不存在内部区域i 1的部分如果代码在标记循环里从 0 开始遍历很可能会用已经被标记的信息去污染其他列。上面的写法因为刻意从range(1, m)和range(1, n)开始天然避开了这个问题。4. 面试官高频追问与作答思路4.1 为什么不让你开辟 O(mn) 的数组这道题在 LeetCode 原题描述里其实有个“进阶Follow up”提示能不能设计一个 O(mn) 时间、O(1) 空间的算法面试官追问 O(1) 空间真正想考察的是你有没有“数据复用”的意识。在工业场景里矩阵规模一大额外开一行一列数组虽然只占 O(mn)但和大规模分布式系统中的内存紧张、缓存失效问题性质相同能不额外开空间就不额外开空间。你回答的时候不要只说“能优化成 O(1)”而要补一句“因为我们发现第一行和第一列本身就是要被清零的候选者拿它们当存储载体不会丢失额外信息”。面试官想听的是这种洞察不是背答案。4.2 回写顺序能不能从左往右这是我最常被问到的一个变体。标准解法第二遍回写是从(1, 1)往后正序遍历而不是倒序。为什么没问题因为我们在标记阶段已经把第一行第一列的信息“固化”成标记位了回写内部区域时只读取matrix[i][0]和matrix[0][j]这两个值在回写过程中不会被修改。无论我们从左到右还是从右到左matrix[i][j]改成 0 都不会回头影响第 i 行的行标记或第 j 列的列标记。真正需要倒序回写的是另一种写法标记阶段把matrix[0][0]作为一个标记位回写时为了避免第一行被提前改掉才需要倒序。这里我们的两个布尔变量把第一行第一列单独拆出去处理了因此正序倒序都能通过。我个人推荐正序因为更符合直觉调试时也好阅读。4.3 如果不能用第一行第一列还能怎么做到 O(1)这道题还有更进阶的变形如果原题约束“第一行和第一列中的元素不允许被修改”怎么办那就只能用“外部单变量 内部标记”的混合策略用一个额外变量col0记录第一列是否需要清零用matrix[0][0]记录第一行是否需要清零再用矩阵内部的第一行、第一列标记其他行列。本质上还是“数据复用”只是把第一行第一列当成一个组合标记区多牺牲一个变量的可读性。这个变形在一般面试里不会出现但如果你能顺口说出来会给面试官留下“学过、看过、懂原理”的印象。4.4 追问矩阵稀疏时的进一步优化如果矩阵非常大但 0 很少比如 10000 x 10000 的矩阵只有 3 个 0你会怎么做答案不是追求 O(1) 空间而是追求更少的时间。此时可以遍历一次矩阵把所有 0 的行号和列号分别存入两个集合空间复杂度 O(非零行数 非零列数)在稀疏场景下接近 O(1)时间上也可以只对需要改动的行和列进行回写避免无脑扫全矩阵。这种追问没有标准答案面试官看的是你是否能根据数据特性调整策略。刷题不能只背最优解要理解不同方案在不同数据分布下的取舍。5. 从 73 题延伸出去刷题与面试的实战心得5.1 四个相关联的 LeetCode 题目对比矩阵置零不是孤立的题它和很多矩阵类题目共享一套“原地修改”的思考方式题目核心考点与 73 题的关系LeetCode 48 旋转图像原地旋转、四元素交换都强调就地修改不能开新矩阵LeetCode 289 生命游戏复合状态、原地同步更新用临时状态编码“新值和旧值”LeetCode 54 螺旋矩阵边界收缩、方向控制矩阵遍历的另一个经典套路LeetCode 200 岛屿数量DFS/BFS 联通块矩阵问题的深度优先遍历思路尤其是 289 生命游戏和 73 题有异曲同工之妙它要求所有格子同时更新根据旧状态决定新状态如果边改边遍历同样会污染后续判断。通用的解决模板就是先标记用特殊值或额外状态再统一回写。5.2 我在实际面试和刷题中的几点体会刷这道题的过程中我自己总结了几个教训分享给你。第一第一遍先写 O(mn) 的标记数组版本再问面试官“需要继续优化到 O(1) 吗”这是一种安全的面试节奏。因为有相当一部分面试官其实只要求 O(mn) 的答案你直接抛 O(1) 的复杂版本反而可能在细节上翻车。当然如果对方明确要求空间 O(1)你再把这里的“标记板”思路写出来。第二多跑几个小样例再提交。我见过太多同学写完这段代码直接提交第一次就 Accepted以为自己无敌了换一个带边角的用例就懵了。建议在本地用 3x3、单行、单列、全零、无零这五类用例各跑一遍十秒钟的事能省去很多 Debug 时间。第三不要用 Python 奇技淫巧。比如有人会用zip(*matrix)转置矩阵来操作看起来很帅但对于这种原地修改题转置会引入额外开销不说还极易写出难以理解的代码。面试官要的是稳定可维护的工程风格不是炫技。第四把注释写到“为什么”而不是“是什么”。比如row0_has_zero False这句很多人的注释是“记录第一行是否有 0”这没有价值好的注释是“这里必须提前记录否则第一行在标记阶段被修改后信息就丢了”。面试官看代码时这种注释能让他一眼看出你理解了题目的坑。最后再说一个很多题解不会提的技巧如果你在面试时紧张第一遍写出来的for循环范围搞混了别急着撕掉重写。先在心里走一遍 3x3 的用例把第一行、第一列、内部区域的下标范围划清楚再落笔。矩阵类题目的下标错误占我当年面试失误的一半以上慢一点稳一点反而更快。这道题刷透了矩阵原地修改这一整类题目都会顺畅很多。接下来你可以拿 289 生命游戏练练手感受一下同一个套路在不同题目里的实际威力。
