LeetCode 73 矩阵置零：O(1) 空间原地算法详解

Leetcode 73 矩阵置零这道题我从第一次刷到它就印象深刻。表面上是道“给定矩阵把含0的行列都清零”的签到题可一旦面试官追问“能不能用O(1)额外空间”它就瞬间变成一堵墙卡住不少刷了 LeetCode 热门100题一多半的人。我见过很多人在周赛或模拟面试遇到这道题时第一反应就是开两个数组记录等被要求原地处理时当场卡壳。这篇文章就把这道题从暴力到最优解彻底拆开讲清楚每一步为什么这么做以及那些你大概率会踩的坑。先直接说结论这题的核心难点不是“怎么把0扩散”而是“怎么记住哪些行列要清零又不占用额外空间”。如果你只是照着题解把代码背下来下次换一道类似题还是不会。所以我会从最朴素的思路讲起逐步推到那个经典的“用第一行第一列做标记”的解法再把实现中容易出错的三四个细节单独拉出来聊。无论你是刚开始刷 LeetCode 的新手还是准备面试想巩固数组题型的进阶选手这篇文章都能帮你把这题吃透。1. 题目理解与思路拆解1.1 题目到底在问什么矩阵置零的要求很简单给定一个 m 行 n 列的矩阵如果某个元素是 0就把这个元素所在的行和列上所有元素都改成 0。听起来像是一个“扩散”操作但注意最后结果里的 0 可能来源于两种情况一是矩阵原本就有的 0二是被同行同列“传染”的 0。这两个来源如果不区分很容易在实现时出现连锁反应。举个例子1 2 3 4 0 6 7 8 9中间那个 0 会导致整个第二行和第二列都变成 0结果就是1 0 3 0 0 0 7 0 9这里有个关键陷阱你不能一边遍历一边立刻把看到的 0 扩散开因为扩散出去的 0 会被当成“原本的 0”继续传染别的行列最后整块矩阵都可能变成 0。我第一次用最笨的双循环时就是遍历到第一个 0 就立刻改整个行和列结果后面的判断全乱套了。所以正确姿势是先记录再修改。那“记录”记录在哪里最简单当然是额外开两个布尔数组一个标记需要清零的行一个标记需要清零的列。但 LeetCode 这道题明确要求“原地修改”并且高阶面试会追问 O(1) 额外空间。这就逼着我们想别的办法。1.2 空间复杂度的三个台阶这道题的空间复杂度演化基本就是一个典型的“从直观到优雅”的路径我建议你按这三步去理解而不是直接背最终解法。第一台阶O(mn) 的副本法。复制一份原矩阵然后遍历原矩阵发现某个位置是 0就去副本里把对应行和列清 0。最后把副本赋值回原矩阵。好处是逻辑无比清晰坏处是空间浪费大面试里这么写基本会被问“能不能优化”。第二台阶O(mn) 的标记数组法。开一个长度为 m 的布尔数组 row一个长度为 n 的布尔数组 col。先扫一遍矩阵遇到 matrix[i][j] 0就把 row[i] 和 col[j] 都置为 true。遍历结束后再根据这两个数组把对应行和列置 0。这是大多数刷题网站官方题解给的“标准普适解”也是面试时最不容易出错的方案。第三台阶O(1) 的原地标记法。既然要额外空间那就只能从矩阵“借”地方。常用做法是利用第一行和第一列来标记剩余区域如果某个元素在第 i 行第 j 列是 0我们就把 matrix[i][0] 和 matrix[0][j] 置为 0作为标记。这样遍历一遍后标记信息就存在矩阵的边框上不需要额外数组。但问题来了第一行和第一列本身可能也是要被清零的对象怎么区分“标记用的0”和“原本就应该被清零的0”这就要用到两个额外的布尔变量来记住第一行和第一列原本是否含 0或者换一种记忆顺序我后面第三节详细说。可以看到空间复杂度从 O(mn) 一路降到 O(1)每次优化都是用“复用已有存储”来换额外空间。这也是面试官最想看到的思考路径。1.3 为什么偏偏选中第一行第一列你可能会好奇原地标记时为什么非要用第一行和第一列当“记录板”不能随便挑一行一列吗理论上可以但挑第一行和第一列有三个好处它们天然是矩阵的“边框”在遍历内层元素时它们作为标记区域和被修改区域可以分离处理最后清零时我们需要遍历整个矩阵而第一行第一列的位置不参与内层循环避免了“边标记边清理”的冲突代码实现最简洁只需要额外用两个变量记住“第一行原本是否含0”和“第一列原本是否含0”就能把标记信息和原始信息区分开。一句话用矩阵自身的边界存储信息就像把备忘录贴在黑板边上既不会挡住黑板内容又方便最后擦掉。2. 三种解法详解与选择建议2.1 标记数组法最稳的O(mn)实现这个解法是很多人最先接触到的标准答案。逻辑分三步遍历矩阵检查每个元素记录需要清零的行号和列号再次遍历矩阵如果当前行号或列号被标记过就置为0结束。用代码表示就是def setZeroes(matrix): m, n len(matrix), len(matrix[0]) row_mark [False] * m col_mark [False] * n for i in range(m): for j in range(n): if matrix[i][j] 0: row_mark[i] True col_mark[j] True for i in range(m): for j in range(n): if row_mark[i] or col_mark[j]: matrix[i][j] 0这套代码的核心在于“先记录、后修改”完全避免了连锁反应。时间复杂度 O(mn)空间复杂度 O(mn)。这个方法最值得记住的是它把“判断条件”和“修改动作”拆开了。如果你觉得原地标记法容易出错完全可以先写这个方案再尝试优化空间。面试时能清晰讲出这个方案的演进路径比直接背最优解更让面试官认可。2.2 原地标记法O(1)空间的经典思路原地标记法的核心是“用第一行和第一列作为标记数组”。但要注意标记区域自己也可能被污染所以需要额外两个变量先记录第一行、第一列是否原本有 0。算法流程如下。第一步判断第一行和第一列是否有 0分别存入 row_has_zero 和 col_has_zero。注意这个判断要在任何修改之前做否则第一行第一列先被改成 0后面的判断全错。第二步从第二行第二列开始遍历矩阵如果 matrix[i][j] 0就把 matrix[i][0] 和 matrix[0][j] 置为 0。第三步再遍历一次内层区域从第二行第二列开始如果 matrix[i][0] 0 或者 matrix[0][j] 0就把 matrix[i][j] 置为 0。第四步根据第一步记录的两个布尔值最后决定是否把第一行和第一列全部置 0。这个顺序非常关键一定是“先标记再清理内层最后清理边框”。为什么因为清理内层时我们需要读取标记信息如果先把第一行第一列清 0标记就丢了。我自己第一次写的时候就是第四步放在了第三步前面内层已经全部清完后才想起来第一行第一列还没按原始情况处理结果现场debug找了半天。记住这个顺序面试时能少很多麻烦。2.3 一种减少变量的奇技淫巧这里分享一个进阶小技巧让代码少用一个变量。思路是用第一列标记哪些行要清零用第一行标记哪些列要清零。但第一行第一列交叉的那个位置 matrix[0][0] 会同时代表“第一行有0”和“第一列有0”这就冲突了。解决办法是用 matrix[0][0] 表示第一行是否有 0再用一个额外变量 col0 表示第一列是否有 0。这样只需要一个额外变量而不是两个。实现时注意一个细节遍历时要从左到右、从上到下遇到 matrix[i][j] 0 时除了设置 matrix[i][0] 和 matrix[0][j] 外如果 j 0还要把 col0 置为 True。最后清零阶段先处理内层再处理第一行最后根据 col0 决定是否清第一列。这个优化版本代码更紧凑但不易读。我的建议是面试时优先写思路清晰的“两个变量版”能写出“一个变量版”是加分项前提是你真懂而不是背。3. 实操过程与代码实现3.1 基础版本完整可运行的O(mn)代码我会给你一份完整代码加上注释方便你直接跑 LeetCode 提交。def setZeroes(self, matrix): m, n len(matrix), len(matrix[0]) rows [False] * m cols [False] * n for i in range(m): for j in range(n): if matrix[i][j] 0: rows[i] True cols[j] True for i in range(m): for j in range(n): if rows[i] or cols[j]: matrix[i][j] 0这段代码有两个细节值得注意第一行第一列同样参与判断不需要特殊处理因为我们的标记数组覆盖了所有行和列修改时直接赋值即可不需要考虑会不会二次传染因为标记数组是独立的。如果你在笔试或手机环境里快速做题这个版本效率足够。LeetCode 上运行时间通常排在前10%左右没有明显性能问题。3.2 原地版逐行讲解的关键代码下面这段是 LeetCode 官方推荐的 O(1) 额外空间解法。我会先列出代码再逐段解释。def setZeroes(self, matrix): m, n len(matrix), len(matrix[0]) first_row_has_zero False first_col_has_zero False for j in range(n): if matrix[0][j] 0: first_row_has_zero True break for i in range(m): if matrix[i][0] 0: first_col_has_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_has_zero: for j in range(n): matrix[0][j] 0 if first_col_has_zero: for i in range(m): matrix[i][0] 0关键点拆解第一个循环先扫描第一行第二个循环扫描第一列。为什么是两段而不是一段因为如果你用一个循环同时检查第一行和第一列可能会出现 matrix[0][0] 是 0 的情况既影响行标记又影响列标记。分成两段逻辑上更清楚。第三个循环从 (1,1) 开始发现矩阵内部有 0 就把它对应的第一行第一列位置变成标记。这里有一个天然优势第一行第一列的原始状态已经被记录过了现在可以随便改。第四个循环再扫描内部根据标记信息清 0。注意这里判断的是matrix[i][0] 0 or matrix[0][j] 0意思是“这一行被标记过或者这一列被标记过那么当前位置就要清 0”。逻辑和 O(mn) 里的rows[i] or cols[j]完全一致只是存储位置从额外数组换成了矩阵边框。最后两步恢复第一行第一列的真实状态。如果原先第一行有 0就把第一行全部清 0如果第一列原先有 0同理。这两个操作必须放在最后因为前面的标记信息就住在第一行第一列你不能提前擦掉备忘录。3.3 验证由正确性到时间空间复杂度我们拿一个含多个 0 的矩阵走一遍0 1 2 0 3 4 5 2 1 3 1 5第一行扫描发现 matrix[0][0]0于是 first_row_has_zeroTrue第一列扫描同样在 matrix[0][0] 发现 0first_col_has_zeroTrue。第三循环从 (1,1) 开始没有发现任何内部 0因为唯一的 0 在第一行和第一列——这正好验证了我们的处理不对内部做冗余操作。第四循环扫描内部matrix[1][0] 和 matrix[0][1] 都不是 0所以矩阵内部的 4,5,2,3,1,5 都不需要清 0。最后根据两个布尔值把第一行和第一列全部清 0。结果变成0 0 0 0 0 4 5 2 0 3 1 5这和我们期望的一致第一行原本有两个 0所以整个第一行都变 0第一列原本有 0所以整个第一列都变 0。内部没有 0 所以保持不变。时间复杂度上我们一共进行了大约三次全矩阵遍历也就是 O(3mn) O(mn)和额外空间法没有本质区别。空间复杂度只用了两个布尔变量O(1)。这就是这道题的最优空间。4. 常见问题与排查技巧实录4.1 最容易踩的坑第一行和第一列被提前清零这是原地写法里发生率最高的问题没有之一。很多人会写出这种顺序# 错误示范 for i in range(m): for j in range(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 # 如果这时直接清第一行第一列标记就没了 for j in range(n): matrix[0][j] 0 for i in range(m): matrix[i][0] 0你会发现问题很大如果在处理内部之前就把第一行第一列给清了后面的第四步判断全都是在读已经被改过的标记结果矩阵会大面积误伤。比如原本只有 (1,1) 一个 0经过上面的错误代码matrix[1][0] 和 matrix[0][1] 都被标记了但如果你先把第一行全部清 0那么第一列原本的标记可能还好但整个第一行不仅被清 0还可能影响 matrix[0][j] 作为“列标记”的值导致后面内部判断时以为某些列都有 0结果整列被误清。解决办法只有一个先记录第一行第一列的原始状态再开始标记和清理最后才根据记录恢复边框。这个顺序是原地法的灵魂。我自己刷题时一旦写错就会在思维上强制自己重复“记录 - 标记 - 清理内部 - 恢复边框”四个阶段每一阶段只做一件事不要混在一起。4.2 边界案例空矩阵和单行/单列矩阵LeetCode 的测试用例不会给空矩阵但面试官可能追问。如果 matrix 是空列表len(matrix[0])会直接报错。所以稳妥做法是在函数开头加一个判空if not matrix: return单行或单列时原地写法照样能跑。比如一个一行三列的矩阵[[1,0,1]]先检查第一行是否有 0found True第一列检查只有一列matrix[0][0] 不是 0所以 first_col_has_zeroFalse内层遍历范围是从 (1,m) 和 (1,n)此时 m1循环范围是空所以第三步什么都不做第四步同理什么都不做最后因为 first_row_has_zeroTrue把整行清 0得到[[0,0,0]]。这个逻辑是自洽的。但如果 m1你遍历内层时使用了 range(1, m)而 range(1,1) 是空的所以不会越界。这也是为什么原地写法的下标从 1 开始是安全的。4.3 不一定要背代码理解标记法的“类比记忆”刷题时最怕背了忘忘了背。我建议你把原地标记法想象成“黑板报”第一行和第一列是黑板边框用来写备忘内部元素是正文遇到 0 就在对应边框上画个记号画完记号后按记号的指示修改正文最后擦掉记号然后根据一开始拍的照片两个布尔变量把边框上原本该清的地方清掉。这个类比能帮你快速回忆流程顺序面试时也不用拿着代码念而是能用自己的话讲清楚。实际上很多 LeetCode 热门题解里也用了类似比喻但关键是一旦你真正理解了标记的“暂存”性质就不会搞混顺序了。4.4 高效调试如何快速定位错误如果提交 LeetCode 时结果不对我建议按这个顺序排查先出最小的测试用例比如一个 2x2 矩阵[[1,1],[1,0]]手动模拟一遍看是标记阶段错还是清理阶段错打印中间态。在每一步循环后输出矩阵当前状态能立刻发现第一行第一列是否被提前修改检查循环边界。最容易写错的是for i in range(1, m)忘记从 1 开始结果把边框给扫进去造成误判确认or逻辑。判断是否需要清零时行标记和列标记只要有一个为 0 就要清不要写成and。我在 LeetCode 讨论区看到很多新手在第四步写成if matrix[i][0] 0 and matrix[0][j] 0那意思是“这一行和这一列同时有 0 才清”显然不对会漏掉大量该清的位置。这种细节最隐蔽也最值得提醒。5. 延伸思考从矩阵置零到实际工程这道题本身是个面试题但它的思路在工程里也有影子。比如数据处理中常常会遇到“某个字段为 0 或空值就需要将整行整列标记为无效”的场景。你完全可以用类似的方式先在内存中维护一个布尔数组记录哪些行哪些列命中条件再去批量更新。如果是海量数据行和列特别多额外数组占内存这时也可以借用第一行第一列作为位图标记不过实际中需要小心是否允许修改原始数据。还有一题非常相似的是 LeetCode 上关于“生命游戏”的那道题同样需要原地更新且避免覆盖旧状态也是用额外的状态值比如 0/1/2/3来暂存新状态。矩阵置零里的“标记与修改分离”思想在那边同样适用。刷题不能只背答案要理解“答案背后的复用思维”以后遇到“不能开额外空间但需要记住状态”的题你都会直接想到这一类解法。我个人在实际操作中的体会是这种数组原地标记题快则半天掌握慢则一周反复出错都正常。犯错本身不是坏事关键是每次报错后你都要能说清楚“是边界问题、顺序问题还是逻辑问题”。如果你能把这三种错误类型各自记住一个典型案例那比单纯刷十道题都管用。最后分享一个小技巧如果你在面试卡壳不妨先跟面试官说“我能用 O(mn) 空间先想一个简单的”然后把标记数组法写出来。接着再说“我再优化一下空间”从标记数组平滑过渡到原地标记。这种渐进式思考很加分因为面试官想看到的不是背答案而是解决问题的能力。矩阵置零就是一道特别适合展示这种能力的题一定要把这个过程练熟。