复杂度的完整推导)
刷算法题的人应该都遇到过这样一道“看起来简单写起来全是坑”的矩阵题给定一个 m×n 的矩阵一旦发现某个元素等于 0就要把它所在的整行和整列全部变成 0。题目编号 73通常被叫做“矩阵置零”。第一眼看到时你会觉得这不就是遍历一遍把有零的行和列记下来再统一置零吗但真正动手做才会发现如果题目要求原地算法、额外空间为 O(1)事情就完全不一样了。这篇文章不打算只贴一个能过的答案而是把从暴力到原地的整个推导过程、边界设计、面试考察点都拆给你看。无论你是正在准备算法面试还是工作中要写这种“不允许随便开大数组”的矩阵处理逻辑都应该能从里面拿到一点实在的东西。1. 题目拆解为什么“原地”和“O(1)”才是真正的考点1.1 题目到底在问什么矩阵置零的规则很简单设矩阵为 matrix尺寸为 m 行 n 列。扫描整个矩阵只要发现 matrix[i][j] 0那么第 i 行的 n 个元素全部置为 0第 j 列的 m 个元素也全部置为 0。注意这个“全部”是最终效果不是扫描过程中的临时状态。比如一个 2×2 矩阵 [[1,0],[1,1]]处理完应该是 [[0,0],[1,0]]。为什么 (1,0) 位置是 0因为它所在列的上一行有一个 0所以整列要清零。这里容易踩的一个直觉陷阱是“边扫边改”。如果一边扫描一边直接置零那么前面某个 0 产生的“新 0”会被当成原始 0导致整个矩阵被全部清零。举个例子矩阵 [[0,1],[1,1]]扫描到 matrix[0][0] 是 0立刻把第一行和第一列改成 0那么 matrix[1][0] 会变成 0再继续扫描时你以为这里原本有 0于是又把第二行也清零了。最终整个矩阵全 0而正确答案是 [[0,1],[0,1]]。所以这道题首先要解决的是“如何区分原始 0 和后来产生的 0”或者“如何在不破坏原始信息的前提下延迟置零”。1.2 “能跑”不等于“合格”空间复杂度的意义很多人把这道题当成“会写就行”但面试官真正想看的是在内存受限的情况下你还能不能做。原地算法要求额外使用的空间是常数级别也就是不能依赖矩阵的规模增长。为什么会有这种要求因为在真实系统中矩阵可能非常大比如一张遥感图像、一个稀疏矩阵的稠密存储、一张用户行为表如果每次处理都要复制一份同等大小的内存代价可能是不可接受的。有的场景甚至不允许额外开一个长度为 mn 的数组因为 mn 随着数据规模无限增长。只有 O(1) 额外空间才意味着无论输入多大真正额外吃掉的只有几个变量。这就是“原地”二字的工程意义不只是炫技。注意这里说的 O(1) 空间通常不考虑输入矩阵本身占用的空间。把所有逻辑建立在“已经给了我这个矩阵我可以直接改它”的前提下。2. 先易后难三条递进解法为什么必须走到第三步2.1 暴力拷贝先复制一份再说最直接的思路是复制一份矩阵。比如copy [row[:] for row in matrix]然后扫描复制矩阵一旦找到 0就在原矩阵上把对应行和列置零。这个做法的好处是逻辑极其简单原始 0 和新产生的 0 被天然隔离了因为判断依据来自副本修改发生在原矩阵上。但代价是额外空间 O(mn)。如果题目没限制空间这段代码确实能在几秒内写出来并通过。但在面试场景里我不建议第一版就给出这种解法。原因有两个第一它没有利用题目给的机会题目考察的核心就是常数额外空间你直接开一个 m×n 的副本等于把最简单的答案丢出来面试官会立刻追问“能不能优化”第二在实际工程中这种“为了处理几个 0 就复制整个矩阵”的做法非常浪费。它适合作为思考起点帮助理解“为什么需要延迟置零”但它不是终点。2.2 标记数组O(mn) 空间的过渡思路比暴力拷贝稍微收敛一点的方案是用两个一维数组。开一个长度为 m 的布尔数组标记哪些行需要清零再开一个长度为 n 的布尔数组标记哪些列需要清零。先遍历矩阵如果遇到 matrix[i][j] 0就把 row_flag[i] 和 col_flag[j] 置为 true。遍历结束后再根据两个标记数组统一把对应行列清零。这个方案空间复杂度是 O(mn)已经比 O(mn) 好了很多。它也是很多人在现场能写出来的“次优解”。它的优点是逻辑清楚、不容易出错尤其适合作为和面试官讨论的中间步骤。时间复杂度同样是 O(mn)但遍历矩阵的次数是两遍所以常数很小。从 O(mn) 到 O(1) 的距离就在于你能不能想到“把标记数组藏进矩阵自己身上”。这就是下面要讲的原地做法。2.3 原地标记把第一行第一列当成天然台账核心思想其实一句话矩阵的第一行和第一列本身也是一条长度为 n 和 m 的“数组”为什么不用它们来记录哪些行和哪些列需要清零如果你把第一行当作“列标记数组”第一列当作“行标记数组”那么就不需要额外申请空间了。具体来说先遍历矩阵中除第一行、第一列以外的区域发现某个位置是 0就把第 i 行对应的第一列格子 matrix[i][0] 设置为 0把第 j 列对应的第一行格子 matrix[0][j] 设置为 0。等全部扫完第一行和第一列上为 0 的位置就等价于“这一列/这一行需要清零”的台账。但这里立刻会出现一个新的问题第一行和第一列自身也有可能原本就有 0。如果你直接用 matrix[0][0] 同时代表“第一行需要清零”和“第一列需要清零”信息就会冲突。比如 matrix[0][0] 原本是 0你怎么知道是第一行需要清零还是所谓台账被某个 matrix[i][0] 置成 0所以必须用额外的一两个变量先把第一行和第一列原本是否存在 0 记录下来之后再去覆盖它们。这就是为什么“O(1) 空间”还保留了“两个变量”的原因。3. 原地 O(1) 空间解法完整推导与代码实现3.1 整体思路两遍扫描 两个额外布尔值具体流程可以拆成四个阶段先扫描第一行和第一列用两个布尔变量 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。这一步是在利用台账清空内部区域。最后根据 row_has_zero 把第一行整行清 0根据 col_has_zero 把第一列整列清 0。为什么是两遍扫描而不是一遍因为第一遍是“记录”第二遍是“执行”两个阶段必须分开。如果你在记录的同时就去清零剩余区域标记会被新生成的 0 覆盖或混淆。实际上在标记阶段可以顺序扫描如果扫描到已经被标记为 0 的 matrix[0][j]不会影响后续因为标记已经写好了。但为了逻辑清晰还是建议先完整标记再统一清理。3.2 为什么第一行和第一列要单独“隔离”直观地说第一行和第一列在这个解法里承担了双重身份它们既是要被处理的矩阵的一部分又是记录标记的“黑板”。黑板和黑板上的内容不能混为一谈。如果没有预先记录范围后面就无法知道第一行第一列里哪些 0 是原始 0哪些 0 是标记出来的。这个隔离思想本质上和“数据库事务里不能边写日志边覆盖日志”是同一个道理先保存元信息再修改数据最后用元信息恢复状态。举一个更具体的场景假设第一行的 matrix[0][2] 原本是 0这代表第 2 列需要被清零。如果在标记阶段你因为某个内部元素把 matrix[0][2] 也设置为 0那么第一行上的这个 0 到底是“原始需求”还是“内部元素的标记”如果不先记录就不能区分最后可能把第 2 列清零的逻辑丢失或重复。用 row_has_zero 和 col_has_zero 把第一行第一列的原始状态先记下来后面的覆盖就可以放心进行。3.3 代码实现一版直接能过的 Pythondef set_zeroes(matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) row_has_zero False col_has_zero False for j in range(n): if matrix[0][j] 0: row_has_zero True break for i in range(m): if matrix[i][0] 0: 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 row_has_zero: for j in range(n): matrix[0][j] 0 if col_has_zero: for i in range(m): matrix[i][0] 0这段代码的关键点在于所有内层遍历都从 1 开始也就是把第一行和第一列当作“已隔离”的标记区不让它们参与剩余部分的清零判断否则会出现一个很隐蔽的错误如果在清理剩余区域时顺带处理了第一行或第一列可能把标记本身覆盖掉导致最终结果错乱。当然从技术上说最后才清理第一行/列这个覆盖是允许的但为了减少脑力负担统一从 1 开始是最稳妥的写法。3.4 正确性验证用一个例子完整走一遍拿一个 3×3 矩阵来手动跑一遍[1, 2, 3] [4, 0, 6] [7, 8, 9]先扫描第一行没有 0所以 row_has_zero False。扫描第一列也没有 0col_has_zero False。然后扫描剩余区域发现 matrix[1][1] 0于是把 matrix[1][0] 置为 0把 matrix[0][1] 置为 0矩阵变成[1, 0, 3] [0, 0, 6] [7, 8, 9]注意这里 matrix[0][1] 被覆写成了 0但这只是“列 1 需要清零”的标记。接着清理剩余区域i 从 1 到 2j 从 1 到 2(1,1)matrix[1][0] 已经是 0所以清零。(1,2)matrix[1][0] 是 0所以清零。(2,1)matrix[0][1] 是 0所以清零。(2,2)matrix[2][0] 不是 0matrix[0][2] 也不是 0所以保留 9。得到[1, 0, 3] [0, 0, 0] [7, 0, 9]最后 row_has_zero 和 col_has_zero 都是 False不清理第一行/列。最终结果正确原矩阵中只有 (1,1)0所以第二行和第二列被清空其他位置保留。这个例子能直观看到标记区的覆盖和剩余区域的清理过程。4. 复杂度分析与正确性证明不只是“能过”4.1 时间复杂度为什么是 O(mn)字面看做了四次遍历两次扫描第一行/列 O(nm)一次标记 O((m-1)(n-1))一次清理 O((m-1)(n-1))最后清第一行/列 O(nm)。加起来是 O(2mn) 级别的常数渐进复杂度 O(mn)。面试时可以这样分析每个格子最多被访问常数次矩阵规模增大时操作量随格子总数线性增长。这里顺带解释一个容易混淆的点有人觉得遍历了四次复杂度应该是 O(4mn)其实常数不影响渐进结果。真正重要的是不管矩阵多大我们都只做有限遍完整扫描没有出现嵌套的额外循环。只要你用的是两层 for 循环按行按列访问并且没有在循环体内再去扫描整行整列时间复杂度就不可能变成 O(mn(mn)) 这类更高阶。4.2 空间复杂度如何严格做到 O(1)除了矩阵本身只用了两个布尔变量 row_has_zero 和 col_has_zero。不管 m 和 n 多大额外变量的个数都恒定所以渐近空间复杂度是 O(1)。这里一个容易被挑战的点是你把矩阵本身改写了这不算是“额外空间”。算法中 in-place 修改通常允许复用输入存储。如果不允许修改输入那就另说。另外有些实现会用一个整数变量 col0 代替第二个布尔值把 matrix[0][0] 作为行标记col0 作为列标记这样额外空间更省。这个变体本质上是一样的只是把两个布尔值换成一个整数和 matrix[0][0]。从空间复杂度的角度看两者都是常数空间但两个布尔值的写法更直观也更不容易在面试时写错。我个人更推荐先掌握两个布尔值的版本。4.3 为什么这个解法不会误标、漏标可以分成三种情况来验证某个内部元素 (i,j) 是 0那么它会设置 matrix[i][0] 和 matrix[0][j] 两个标记在清理阶段只要任一标记为 0该格就会被清零所以行和列都被覆盖不会漏。如果某个内部元素 (i,j) 不是 0但它所在的行或者列里有其它 0那么必然有一个标记被置 0清理阶段它也会被清零不会漏。如果 (i,j) 所在的行和列都没有 0但刚好第一行或第一列有 0这个格子会不会被误清不会。因为标记阶段只扫描从第二行开始的区域第一行或第一列自身的 0 只会被记录在 row_has_zero / col_has_zero 里不会去设置 matrix[i][0] 或 matrix[0][j]。内部区域在清理时只参照第一行第一列的标记而这两个标记不会被边界 0 触发所以没有 0 的行列不会被清空。举个容易被误判的例子矩阵 [[0,1],[1,1]]。第一行有 0所以第一行整行清零第一列整列清零。内部区域只有 (1,1)但第一行/列的 0 并不会给内部区域打标记因此 (1,1) 保留为 1。最终结果是 [[0,0],[1,0]]而不是整个矩阵全变成 0。对照代码标记阶段 range(1,2) 里只检查 (1,1)它不等于 0不设置标记清理阶段 (1,1) 两个标记都不是 0保留最后 row_has_zero 和 col_has_zero 为真清第一行和第一列。逻辑完全自洽。5. 实战避坑边界条件、调试技巧与测试用例5.1 最容易踩的三个坑第一个坑是一边扫描一边置零导致新 0 被当成原始 0这个前面已经说透了。第二个坑是先清第一行/列再清理内部区域。如果你在最后分支之前就把第一行或第一列整体清零内部清理时的标记可能全部变成 0导致每个格子都被置 0。正确的顺序一定是先记录、再标记、后清理内部、最后处理第一行和第一列边界。第三个坑是行数为 1 或列数为 1 的情况。当 m 1 或 n 1 时矩阵只有一行或一列循环起点range(1, m)或range(1, n)可能是空。此时需要保证第一次扫描就能正确处理。实际上代码在开头判断if not matrix or not matrix[0]能挡住空矩阵对于一行矩阵row_has_zero 记录第一行是否有 0内层标记循环for i in range(1, 1)不执行清理循环也不执行最后 row_has_zero 为真时直接把这一行全清零正确。一列同理。还有一种隐藏的边界矩阵不是“规整”的矩形比如某一行长度和其他行不同。虽然大部分在线判题的输入都是矩形但真实工程中数据未必规整。这时你的代码不能假设 matrix[0].length 就是所有行的长度最好在进入算法前做一次校验或者直接对每行单独取长度。为了通用性我会在代码开头加一个循环确认每一行的长度一致如果发现不一致再单独处理但这样会增加额外检查时间。面试时通常不需要处理这种不规则矩阵你可以在回答中提一句“假设输入是合法矩形”。5.2 手写题怎么减少“脑供血不足”我自己的习惯是先在草稿纸上画 3×3 的方格把“原始 0”和“标记 0”用不同符号标出来走两遍。第一遍只画标记第二遍只画清理。这个习惯帮我避免了很多“代码看起来对跑起来错”的情况。另一个建议是把中间过程打印出来。如果你在本地调试可以在每次循环后输出矩阵看看第一行第一列的变化是否符合预期。不要嫌麻烦这类原地数组题最难的就是“脑子里维护状态”打印输出是最直接的辅助。具体来说我会在代码里临时加一行print(matrix)在标记阶段结束后和清理阶段结束后各打印一次。如果标记阶段结束后第一行第一列上的 0 恰好对应需要清零的行列说明标记正确如果发现多了一些不应该出现的 0说明扫描范围没有控制好。调试完再把打印语句删掉不影响提交。5.3 必测的边界用例清单写完代码后建议至少跑一遍下面的用例用例输入期望输出普通情况[[1,2,3],[4,0,6],[7,8,9]][[1,0,3],[0,0,0],[7,0,9]]第一行有 0[[0,1],[1,1]][[0,0],[1,0]]第一列有 0[[1,1],[0,1]][[0,1],[0,0]]全 0 矩阵[[0,0],[0,0]][[0,0],[0,0]]无 0 矩阵[[1,2],[3,4]][[1,2],[3,4]]单行矩阵[[0,1,2]][[0,0,0]]单列矩阵[[1],[0],[2]][[0],[0],[0]]对角线上的 0[[1,0],[0,1]][[0,0],[0,0]]为什么单行矩阵的期望是全 0因为这一行里有 0所以整行都清零同时这个 0 所在列也只有这一行列本身也被清零所以结果就是全 0。单列矩阵同理。遇到这些边界用例时代码里的range(1, m)或range(1, n)可能为空但前面的第一行/第一列扫描已经捕获到了 0最后的清理分支仍然会执行所以结果是正确的。6. 面试官视角这道题到底在考察什么6.1 从这道题看算法面试的“分层评价”如果你是面试官你会怎么评价这个解我最看重三点第一候选人能不能想到“延迟处理”也就是先记录后修改第二能不能意识到第一行第一列是天然的资源而不是急于把它当作普通数据第三能不能处理好边界状态。能想到 O(mn) 标记数组的人很多能进一步压缩到 O(1) 的人会明显少一截。这道题很适合做“锚点题”从暴力到 O(mn)从标记到 O(mn)再从原地到 O(1)每一层都对应不同的思维深度。很多候选人一上来就背出了“用第一行第一列做标记”的结论但当我追问“为什么需要额外两个变量记录第一行第一列的原始状态”时他会愣住。这说明他并没有真正理解解法只是记住了代码。面试官其实不怕你慢慢想怕的是你把一个不理解的东西背得滚瓜烂熟。所以我的建议是哪怕第一次写不出来也要把每个标记的含义解释清楚。6.2 常见追问与扩展方向面试官如果继续追问通常会从以下几个方向延展“如果每一轮需要把所有 0 所在的行列同时置零重复 k 次会怎样”这其实是在考察你对“原始 0”和“新 0”的区分能力。重复多次后新产生的 0 会继续影响其它行列模拟时需要把每次的修改结果当作下一次的输入而不是在原矩阵上迭代判断。“假如 m 和 n 相差特别大比如 1e6 × 10你会优化标记数组吗”答案是可以把标记放在较小的维度上或者更进一步把较大维度的行信息放到第一列列的标记仍用 O(n) 数组因为 n 相对小这属于空间权衡。“如果不能修改矩阵本身只允许返回新矩阵怎么处理”那就回到拷贝解法这也是为什么很多题会明确限制 in-place否则答案会简单很多。矩阵类题目里和它配套的还有旋转图像、螺旋矩阵、岛屿数量等它们都不要求你背模板而是要求在纸上推演状态变化。矩阵置零是其中最小巧的一道非常适合用来训练“在已有数据结构上做标记”的思维方式。我甚至会觉得如果能把这道题讲明白很多类似的原地修改题都能很快打通。6.3 如果再进一步当矩阵无法整体加载时怎么办现实场景中矩阵可能大到内存装不下比如几亿行的评分矩阵。这时候再强调 O(1) 内存就有点不真实了因为输入本身都放不进内存。工程上会采用分块处理把矩阵切成若干块扫描每一块用外部存储记录哪些行和列需要清零或者利用稀疏表示只存非零位置最后按行按列计算受影响范围。这个方向已经超出这道题的范围但原理仍然是“先记台账再执行清理”。理解原地解法之后再往分布式或外存算法方向延伸会容易很多。这里也可以联系到“缓存友好性”。即使矩阵能放进内存如果行数特别多连续访问一整行比反复跳跃访问更友好。在实现里两次内层循环都是按行优先的顺序访问也就是先固定 i再遍历 j这样可以更好地利用 CPU 缓存。如果你改成先按列访问性能会有明显下降。这是工程细节面试时主动提一嘴往往是加分项。这道题我反复琢磨过很多遍每次都会叮嘱一个细节先记边界状态再改矩阵最后处理边界。纸上推演三分钟胜过写错三十分钟。如果你第一次写原地版本时翻车了真的不丢人很多人在这里都栽过跟头。最后再分享一个小技巧把“第一行第一列当成白板”这句话写在代码注释里下一次你回看时会立刻理解当初的设计意图。矩阵置零看起来只是一个小题但“用输入自身的冗余空间做标记”这个思想在后续很多高级算法里都会反复出现。
刷算法题的人应该都遇到过这样一道“看起来简单写起来全是坑”的矩阵题给定一个 m×n 的矩阵一旦发现某个元素等于 0就要把它所在的整行和整列全部变成 0。题目编号 73通常被叫做“矩阵置零”。第一眼看到时你会觉得这不就是遍历一遍把有零的行和列记下来再统一置零吗但真正动手做才会发现如果题目要求原地算法、额外空间为 O(1)事情就完全不一样了。这篇文章不打算只贴一个能过的答案而是把从暴力到原地的整个推导过程、边界设计、面试考察点都拆给你看。无论你是正在准备算法面试还是工作中要写这种“不允许随便开大数组”的矩阵处理逻辑都应该能从里面拿到一点实在的东西。1. 题目拆解为什么“原地”和“O(1)”才是真正的考点1.1 题目到底在问什么矩阵置零的规则很简单设矩阵为 matrix尺寸为 m 行 n 列。扫描整个矩阵只要发现 matrix[i][j] 0那么第 i 行的 n 个元素全部置为 0第 j 列的 m 个元素也全部置为 0。注意这个“全部”是最终效果不是扫描过程中的临时状态。比如一个 2×2 矩阵 [[1,0],[1,1]]处理完应该是 [[0,0],[1,0]]。为什么 (1,0) 位置是 0因为它所在列的上一行有一个 0所以整列要清零。这里容易踩的一个直觉陷阱是“边扫边改”。如果一边扫描一边直接置零那么前面某个 0 产生的“新 0”会被当成原始 0导致整个矩阵被全部清零。举个例子矩阵 [[0,1],[1,1]]扫描到 matrix[0][0] 是 0立刻把第一行和第一列改成 0那么 matrix[1][0] 会变成 0再继续扫描时你以为这里原本有 0于是又把第二行也清零了。最终整个矩阵全 0而正确答案是 [[0,1],[0,1]]。所以这道题首先要解决的是“如何区分原始 0 和后来产生的 0”或者“如何在不破坏原始信息的前提下延迟置零”。1.2 “能跑”不等于“合格”空间复杂度的意义很多人把这道题当成“会写就行”但面试官真正想看的是在内存受限的情况下你还能不能做。原地算法要求额外使用的空间是常数级别也就是不能依赖矩阵的规模增长。为什么会有这种要求因为在真实系统中矩阵可能非常大比如一张遥感图像、一个稀疏矩阵的稠密存储、一张用户行为表如果每次处理都要复制一份同等大小的内存代价可能是不可接受的。有的场景甚至不允许额外开一个长度为 mn 的数组因为 mn 随着数据规模无限增长。只有 O(1) 额外空间才意味着无论输入多大真正额外吃掉的只有几个变量。这就是“原地”二字的工程意义不只是炫技。注意这里说的 O(1) 空间通常不考虑输入矩阵本身占用的空间。把所有逻辑建立在“已经给了我这个矩阵我可以直接改它”的前提下。2. 先易后难三条递进解法为什么必须走到第三步2.1 暴力拷贝先复制一份再说最直接的思路是复制一份矩阵。比如copy [row[:] for row in matrix]然后扫描复制矩阵一旦找到 0就在原矩阵上把对应行和列置零。这个做法的好处是逻辑极其简单原始 0 和新产生的 0 被天然隔离了因为判断依据来自副本修改发生在原矩阵上。但代价是额外空间 O(mn)。如果题目没限制空间这段代码确实能在几秒内写出来并通过。但在面试场景里我不建议第一版就给出这种解法。原因有两个第一它没有利用题目给的机会题目考察的核心就是常数额外空间你直接开一个 m×n 的副本等于把最简单的答案丢出来面试官会立刻追问“能不能优化”第二在实际工程中这种“为了处理几个 0 就复制整个矩阵”的做法非常浪费。它适合作为思考起点帮助理解“为什么需要延迟置零”但它不是终点。2.2 标记数组O(mn) 空间的过渡思路比暴力拷贝稍微收敛一点的方案是用两个一维数组。开一个长度为 m 的布尔数组标记哪些行需要清零再开一个长度为 n 的布尔数组标记哪些列需要清零。先遍历矩阵如果遇到 matrix[i][j] 0就把 row_flag[i] 和 col_flag[j] 置为 true。遍历结束后再根据两个标记数组统一把对应行列清零。这个方案空间复杂度是 O(mn)已经比 O(mn) 好了很多。它也是很多人在现场能写出来的“次优解”。它的优点是逻辑清楚、不容易出错尤其适合作为和面试官讨论的中间步骤。时间复杂度同样是 O(mn)但遍历矩阵的次数是两遍所以常数很小。从 O(mn) 到 O(1) 的距离就在于你能不能想到“把标记数组藏进矩阵自己身上”。这就是下面要讲的原地做法。2.3 原地标记把第一行第一列当成天然台账核心思想其实一句话矩阵的第一行和第一列本身也是一条长度为 n 和 m 的“数组”为什么不用它们来记录哪些行和哪些列需要清零如果你把第一行当作“列标记数组”第一列当作“行标记数组”那么就不需要额外申请空间了。具体来说先遍历矩阵中除第一行、第一列以外的区域发现某个位置是 0就把第 i 行对应的第一列格子 matrix[i][0] 设置为 0把第 j 列对应的第一行格子 matrix[0][j] 设置为 0。等全部扫完第一行和第一列上为 0 的位置就等价于“这一列/这一行需要清零”的台账。但这里立刻会出现一个新的问题第一行和第一列自身也有可能原本就有 0。如果你直接用 matrix[0][0] 同时代表“第一行需要清零”和“第一列需要清零”信息就会冲突。比如 matrix[0][0] 原本是 0你怎么知道是第一行需要清零还是所谓台账被某个 matrix[i][0] 置成 0所以必须用额外的一两个变量先把第一行和第一列原本是否存在 0 记录下来之后再去覆盖它们。这就是为什么“O(1) 空间”还保留了“两个变量”的原因。3. 原地 O(1) 空间解法完整推导与代码实现3.1 整体思路两遍扫描 两个额外布尔值具体流程可以拆成四个阶段先扫描第一行和第一列用两个布尔变量 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。这一步是在利用台账清空内部区域。最后根据 row_has_zero 把第一行整行清 0根据 col_has_zero 把第一列整列清 0。为什么是两遍扫描而不是一遍因为第一遍是“记录”第二遍是“执行”两个阶段必须分开。如果你在记录的同时就去清零剩余区域标记会被新生成的 0 覆盖或混淆。实际上在标记阶段可以顺序扫描如果扫描到已经被标记为 0 的 matrix[0][j]不会影响后续因为标记已经写好了。但为了逻辑清晰还是建议先完整标记再统一清理。3.2 为什么第一行和第一列要单独“隔离”直观地说第一行和第一列在这个解法里承担了双重身份它们既是要被处理的矩阵的一部分又是记录标记的“黑板”。黑板和黑板上的内容不能混为一谈。如果没有预先记录范围后面就无法知道第一行第一列里哪些 0 是原始 0哪些 0 是标记出来的。这个隔离思想本质上和“数据库事务里不能边写日志边覆盖日志”是同一个道理先保存元信息再修改数据最后用元信息恢复状态。举一个更具体的场景假设第一行的 matrix[0][2] 原本是 0这代表第 2 列需要被清零。如果在标记阶段你因为某个内部元素把 matrix[0][2] 也设置为 0那么第一行上的这个 0 到底是“原始需求”还是“内部元素的标记”如果不先记录就不能区分最后可能把第 2 列清零的逻辑丢失或重复。用 row_has_zero 和 col_has_zero 把第一行第一列的原始状态先记下来后面的覆盖就可以放心进行。3.3 代码实现一版直接能过的 Pythondef set_zeroes(matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) row_has_zero False col_has_zero False for j in range(n): if matrix[0][j] 0: row_has_zero True break for i in range(m): if matrix[i][0] 0: 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 row_has_zero: for j in range(n): matrix[0][j] 0 if col_has_zero: for i in range(m): matrix[i][0] 0这段代码的关键点在于所有内层遍历都从 1 开始也就是把第一行和第一列当作“已隔离”的标记区不让它们参与剩余部分的清零判断否则会出现一个很隐蔽的错误如果在清理剩余区域时顺带处理了第一行或第一列可能把标记本身覆盖掉导致最终结果错乱。当然从技术上说最后才清理第一行/列这个覆盖是允许的但为了减少脑力负担统一从 1 开始是最稳妥的写法。3.4 正确性验证用一个例子完整走一遍拿一个 3×3 矩阵来手动跑一遍[1, 2, 3] [4, 0, 6] [7, 8, 9]先扫描第一行没有 0所以 row_has_zero False。扫描第一列也没有 0col_has_zero False。然后扫描剩余区域发现 matrix[1][1] 0于是把 matrix[1][0] 置为 0把 matrix[0][1] 置为 0矩阵变成[1, 0, 3] [0, 0, 6] [7, 8, 9]注意这里 matrix[0][1] 被覆写成了 0但这只是“列 1 需要清零”的标记。接着清理剩余区域i 从 1 到 2j 从 1 到 2(1,1)matrix[1][0] 已经是 0所以清零。(1,2)matrix[1][0] 是 0所以清零。(2,1)matrix[0][1] 是 0所以清零。(2,2)matrix[2][0] 不是 0matrix[0][2] 也不是 0所以保留 9。得到[1, 0, 3] [0, 0, 0] [7, 0, 9]最后 row_has_zero 和 col_has_zero 都是 False不清理第一行/列。最终结果正确原矩阵中只有 (1,1)0所以第二行和第二列被清空其他位置保留。这个例子能直观看到标记区的覆盖和剩余区域的清理过程。4. 复杂度分析与正确性证明不只是“能过”4.1 时间复杂度为什么是 O(mn)字面看做了四次遍历两次扫描第一行/列 O(nm)一次标记 O((m-1)(n-1))一次清理 O((m-1)(n-1))最后清第一行/列 O(nm)。加起来是 O(2mn) 级别的常数渐进复杂度 O(mn)。面试时可以这样分析每个格子最多被访问常数次矩阵规模增大时操作量随格子总数线性增长。这里顺带解释一个容易混淆的点有人觉得遍历了四次复杂度应该是 O(4mn)其实常数不影响渐进结果。真正重要的是不管矩阵多大我们都只做有限遍完整扫描没有出现嵌套的额外循环。只要你用的是两层 for 循环按行按列访问并且没有在循环体内再去扫描整行整列时间复杂度就不可能变成 O(mn(mn)) 这类更高阶。4.2 空间复杂度如何严格做到 O(1)除了矩阵本身只用了两个布尔变量 row_has_zero 和 col_has_zero。不管 m 和 n 多大额外变量的个数都恒定所以渐近空间复杂度是 O(1)。这里一个容易被挑战的点是你把矩阵本身改写了这不算是“额外空间”。算法中 in-place 修改通常允许复用输入存储。如果不允许修改输入那就另说。另外有些实现会用一个整数变量 col0 代替第二个布尔值把 matrix[0][0] 作为行标记col0 作为列标记这样额外空间更省。这个变体本质上是一样的只是把两个布尔值换成一个整数和 matrix[0][0]。从空间复杂度的角度看两者都是常数空间但两个布尔值的写法更直观也更不容易在面试时写错。我个人更推荐先掌握两个布尔值的版本。4.3 为什么这个解法不会误标、漏标可以分成三种情况来验证某个内部元素 (i,j) 是 0那么它会设置 matrix[i][0] 和 matrix[0][j] 两个标记在清理阶段只要任一标记为 0该格就会被清零所以行和列都被覆盖不会漏。如果某个内部元素 (i,j) 不是 0但它所在的行或者列里有其它 0那么必然有一个标记被置 0清理阶段它也会被清零不会漏。如果 (i,j) 所在的行和列都没有 0但刚好第一行或第一列有 0这个格子会不会被误清不会。因为标记阶段只扫描从第二行开始的区域第一行或第一列自身的 0 只会被记录在 row_has_zero / col_has_zero 里不会去设置 matrix[i][0] 或 matrix[0][j]。内部区域在清理时只参照第一行第一列的标记而这两个标记不会被边界 0 触发所以没有 0 的行列不会被清空。举个容易被误判的例子矩阵 [[0,1],[1,1]]。第一行有 0所以第一行整行清零第一列整列清零。内部区域只有 (1,1)但第一行/列的 0 并不会给内部区域打标记因此 (1,1) 保留为 1。最终结果是 [[0,0],[1,0]]而不是整个矩阵全变成 0。对照代码标记阶段 range(1,2) 里只检查 (1,1)它不等于 0不设置标记清理阶段 (1,1) 两个标记都不是 0保留最后 row_has_zero 和 col_has_zero 为真清第一行和第一列。逻辑完全自洽。5. 实战避坑边界条件、调试技巧与测试用例5.1 最容易踩的三个坑第一个坑是一边扫描一边置零导致新 0 被当成原始 0这个前面已经说透了。第二个坑是先清第一行/列再清理内部区域。如果你在最后分支之前就把第一行或第一列整体清零内部清理时的标记可能全部变成 0导致每个格子都被置 0。正确的顺序一定是先记录、再标记、后清理内部、最后处理第一行和第一列边界。第三个坑是行数为 1 或列数为 1 的情况。当 m 1 或 n 1 时矩阵只有一行或一列循环起点range(1, m)或range(1, n)可能是空。此时需要保证第一次扫描就能正确处理。实际上代码在开头判断if not matrix or not matrix[0]能挡住空矩阵对于一行矩阵row_has_zero 记录第一行是否有 0内层标记循环for i in range(1, 1)不执行清理循环也不执行最后 row_has_zero 为真时直接把这一行全清零正确。一列同理。还有一种隐藏的边界矩阵不是“规整”的矩形比如某一行长度和其他行不同。虽然大部分在线判题的输入都是矩形但真实工程中数据未必规整。这时你的代码不能假设 matrix[0].length 就是所有行的长度最好在进入算法前做一次校验或者直接对每行单独取长度。为了通用性我会在代码开头加一个循环确认每一行的长度一致如果发现不一致再单独处理但这样会增加额外检查时间。面试时通常不需要处理这种不规则矩阵你可以在回答中提一句“假设输入是合法矩形”。5.2 手写题怎么减少“脑供血不足”我自己的习惯是先在草稿纸上画 3×3 的方格把“原始 0”和“标记 0”用不同符号标出来走两遍。第一遍只画标记第二遍只画清理。这个习惯帮我避免了很多“代码看起来对跑起来错”的情况。另一个建议是把中间过程打印出来。如果你在本地调试可以在每次循环后输出矩阵看看第一行第一列的变化是否符合预期。不要嫌麻烦这类原地数组题最难的就是“脑子里维护状态”打印输出是最直接的辅助。具体来说我会在代码里临时加一行print(matrix)在标记阶段结束后和清理阶段结束后各打印一次。如果标记阶段结束后第一行第一列上的 0 恰好对应需要清零的行列说明标记正确如果发现多了一些不应该出现的 0说明扫描范围没有控制好。调试完再把打印语句删掉不影响提交。5.3 必测的边界用例清单写完代码后建议至少跑一遍下面的用例用例输入期望输出普通情况[[1,2,3],[4,0,6],[7,8,9]][[1,0,3],[0,0,0],[7,0,9]]第一行有 0[[0,1],[1,1]][[0,0],[1,0]]第一列有 0[[1,1],[0,1]][[0,1],[0,0]]全 0 矩阵[[0,0],[0,0]][[0,0],[0,0]]无 0 矩阵[[1,2],[3,4]][[1,2],[3,4]]单行矩阵[[0,1,2]][[0,0,0]]单列矩阵[[1],[0],[2]][[0],[0],[0]]对角线上的 0[[1,0],[0,1]][[0,0],[0,0]]为什么单行矩阵的期望是全 0因为这一行里有 0所以整行都清零同时这个 0 所在列也只有这一行列本身也被清零所以结果就是全 0。单列矩阵同理。遇到这些边界用例时代码里的range(1, m)或range(1, n)可能为空但前面的第一行/第一列扫描已经捕获到了 0最后的清理分支仍然会执行所以结果是正确的。6. 面试官视角这道题到底在考察什么6.1 从这道题看算法面试的“分层评价”如果你是面试官你会怎么评价这个解我最看重三点第一候选人能不能想到“延迟处理”也就是先记录后修改第二能不能意识到第一行第一列是天然的资源而不是急于把它当作普通数据第三能不能处理好边界状态。能想到 O(mn) 标记数组的人很多能进一步压缩到 O(1) 的人会明显少一截。这道题很适合做“锚点题”从暴力到 O(mn)从标记到 O(mn)再从原地到 O(1)每一层都对应不同的思维深度。很多候选人一上来就背出了“用第一行第一列做标记”的结论但当我追问“为什么需要额外两个变量记录第一行第一列的原始状态”时他会愣住。这说明他并没有真正理解解法只是记住了代码。面试官其实不怕你慢慢想怕的是你把一个不理解的东西背得滚瓜烂熟。所以我的建议是哪怕第一次写不出来也要把每个标记的含义解释清楚。6.2 常见追问与扩展方向面试官如果继续追问通常会从以下几个方向延展“如果每一轮需要把所有 0 所在的行列同时置零重复 k 次会怎样”这其实是在考察你对“原始 0”和“新 0”的区分能力。重复多次后新产生的 0 会继续影响其它行列模拟时需要把每次的修改结果当作下一次的输入而不是在原矩阵上迭代判断。“假如 m 和 n 相差特别大比如 1e6 × 10你会优化标记数组吗”答案是可以把标记放在较小的维度上或者更进一步把较大维度的行信息放到第一列列的标记仍用 O(n) 数组因为 n 相对小这属于空间权衡。“如果不能修改矩阵本身只允许返回新矩阵怎么处理”那就回到拷贝解法这也是为什么很多题会明确限制 in-place否则答案会简单很多。矩阵类题目里和它配套的还有旋转图像、螺旋矩阵、岛屿数量等它们都不要求你背模板而是要求在纸上推演状态变化。矩阵置零是其中最小巧的一道非常适合用来训练“在已有数据结构上做标记”的思维方式。我甚至会觉得如果能把这道题讲明白很多类似的原地修改题都能很快打通。6.3 如果再进一步当矩阵无法整体加载时怎么办现实场景中矩阵可能大到内存装不下比如几亿行的评分矩阵。这时候再强调 O(1) 内存就有点不真实了因为输入本身都放不进内存。工程上会采用分块处理把矩阵切成若干块扫描每一块用外部存储记录哪些行和列需要清零或者利用稀疏表示只存非零位置最后按行按列计算受影响范围。这个方向已经超出这道题的范围但原理仍然是“先记台账再执行清理”。理解原地解法之后再往分布式或外存算法方向延伸会容易很多。这里也可以联系到“缓存友好性”。即使矩阵能放进内存如果行数特别多连续访问一整行比反复跳跃访问更友好。在实现里两次内层循环都是按行优先的顺序访问也就是先固定 i再遍历 j这样可以更好地利用 CPU 缓存。如果你改成先按列访问性能会有明显下降。这是工程细节面试时主动提一嘴往往是加分项。这道题我反复琢磨过很多遍每次都会叮嘱一个细节先记边界状态再改矩阵最后处理边界。纸上推演三分钟胜过写错三十分钟。如果你第一次写原地版本时翻车了真的不丢人很多人在这里都栽过跟头。最后再分享一个小技巧把“第一行第一列当成白板”这句话写在代码注释里下一次你回看时会立刻理解当初的设计意图。矩阵置零看起来只是一个小题但“用输入自身的冗余空间做标记”这个思想在后续很多高级算法里都会反复出现。
