Leetcode 73矩阵置零这题我在不同阶段刷了至少三遍每次都有新理解。它在 Leetcode 热门 100 题里位置靠前题目描述只有一句话给定一个 m x n 的矩阵如果某个元素为 0则将其所在行和列的所有元素都设为 0并且要求原地修改。很多人第一眼觉得这是道简单题可真要在面试里把常数空间解法讲清楚卡壳的往往是两个地方为什么第一行第一列能当标记以及处理顺序为什么不能乱。这篇文章就把这题彻底拆开从 O(mn) 空间、O(mn) 空间一路讲到 O(1) 空间的矩阵内标记法每一版本都会解释设计动机顺便把实际刷题时见过的错误提交都整理出来。1. 先看懂题目矩阵置零到底在考什么1.1 题目原意到底是什么意思题目输入是一个 m 行 n 列的整数矩阵。要求是遍历这个矩阵只要发现某个位置 (i, j) 上的值是 0就把第 i 行整行和第 j 列整列全部变成 0。注意这个规则是“连锁式”的多个 0 互相影响但只需要考虑原始矩阵里的 0不需要考虑因为置零新产生的 0。举个例子输入 [[1, 1, 1], [1, 0, 1], [1, 1, 1]] 输出 [[1, 0, 1], [0, 0, 0], [1, 0, 1]]矩阵正中间有一个 0所以中间行、中间列全部被置零四个角保持不变。再来看一个多 0 的例子输入 [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] 输出 [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]左上角和右上角都是 0所以第一行、第一列、第四列都被置零。中间那些元素因为不在任何带 0 的行或列上所以保留原值。题目还有一个硬性要求原地修改。也就是说不能用额外矩阵去存结果必须在传入的这个二维数组上直接改。Leetcode 上现在的数据范围里 m、n 一般到 200 以内元素是 int 类型。正因为尺寸不大时间复杂度和空间复杂度的优化就变成了这道题唯一的考察重点。1.2 为什么是高频题Leetcode 热门 100 题里收录它面试题库里也常见它原因很实际。第一读题没有门槛不需要任何算法背景几分钟就能让候选人进入状态。第二它背后藏着一组漂亮的复杂度梯度复制矩阵是 O(mn) 空间标记数组是 O(mn) 空间矩阵内标记是 O(1) 空间。面试官可以用同一道题通过“还能不能更省”这句话一层层测出你优化方案的思路能力。第三也是最重要的一点它考察的是“原地修改时的信息覆盖问题”。数据要存在原数组里又要用原数组传递状态这本来就是工程里很常见的矛盾。很多系统设计、缓存策略、内存复用场景都会遇到类似问题。而矩阵置零恰好把这个矛盾压缩到最小规模让候选人用一小段代码展示自己处理这种问题的意识。会做这题的人不少但能在几分钟内把原理讲清楚、把顺序问题避开的候选人确实不算多。2. 从最笨的解法到 O(mn) 空间2.1 复制矩阵能跑但不是最优最容易想到的方案是复制一份原矩阵然后遍历副本发现某个位置是 0就去原矩阵里把它所在的行和列全部置零。def set_zeroes_copy(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 r in range(m): matrix[r][j] 0 for c in range(n): matrix[i][c] 0这版代码思路直白人不会写错但它有两个问题。空间上复制一份完整矩阵要 O(mn) 的额外内存时间上虽然主循环是 O(mn)但每次遇到 0 都要扫一行和一列最坏情况下矩阵全是 0会退化到 O(mn * (mn))。这个版本的价值只在于作对比。如果你在面试里写它面试官大概率会追问“能不能不复制”然后顺势引到更优解法。所以它适合作为一个思考起点但不适合作为最终提交。2.2 行、列标记数组O(mn) 空间的中间解复制矩阵缺点明显于是自然会想到我们不复制整张矩阵只记录“哪些行需要清零、哪些列需要清零”。这就是两个标记数组的思路。def set_zeroes_linear(matrix): m, n len(matrix), len(matrix[0]) row_zero [False] * m col_zero [False] * n for i in range(m): for j in range(n): if matrix[i][j] 0: row_zero[i] True col_zero[j] True for i in range(m): for j in range(n): if row_zero[i] or col_zero[j]: matrix[i][j] 0这个解法是两遍扫描第一遍做标记第二遍根据标记修改矩阵。空间复杂度降到了 O(mn)时间复杂度稳定在 O(mn)已经是一个很理想的答案了。为什么第一遍必须先标记、第二遍再修改因为如果在第一遍里发现 0 就立刻把整行整列置零那么新产生的 0 会干扰后续的判断比如一个本来不该清零的行会因为另一个行被清零后产生出的 0 而被误判。标记数组本质上是把“哪些位置需要处理”这个信息先完整地记录下来避免修改过程中的副作用互相干扰。这个“先记录、后执行”的思想也是接下来常数空间解法的灵魂。2.3 三种方案的空间复杂度对比把三种思路放在一张表里看梯度非常清楚解法时间复杂度额外空间是否原地适用场景复制矩阵最坏 O(mn(mn))O(mn)否只作为保底思路行、列标记数组O(mn)O(mn)是面试中可先给出逻辑最清晰矩阵内标记O(mn)O(1)是最终推荐省空间且体现优化能力注意时间复杂度下限就是 O(mn)因为你至少要把每个元素看一遍才知道它是不是 0。所以后两种方案在时间上已经做不出区别比拼的就是谁能在空间上再抠出一个量级。而常数空间的解法依赖的是同一个矩阵里“第一行”和“第一列”这两块区域来存储标记信息。3. 常数空间的矩阵内标记法3.1 把第一行第一列当成“公告栏”既然需要 O(mn) 的标记信息而矩阵里本身就有 m 行和 n 列一个自然的想法是用矩阵自己的第一行来标记每一列是否需要清零用第一列来标记每一行是否需要清零。也就是说把第一行和第一列当作一个“公告栏”。具体规则是这样的扫描矩阵内部从第二行第二列开始如果发现 matrix[i][j] 0就在公告栏上写两个信息——matrix[i][0] 0 表示第 i 行需要清零matrix[0][j] 0 表示第 j 列需要清零。为什么这个方案不会出错因为公告栏上的每个 0 都对应一个真实存在的 0 所在的行或列。比如 matrix[i][0] 被写成 0是因为第 i 行内部确实有一个 0那么第 i 行整行清零本来就是正确操作matrix[0][j] 被写成 0是因为第 j 列内部确实有一个 0那么第 j 列整列清零也没有问题。所以标记过程并不会制造“错误信号”。但公告栏有个特别坑的地方matrix[0][0] 这个位置同时属于第一行和第一列。它到底是“第一行有 0”的标记还是“第一列有 0”的标记单看这个位置无法区分。所以必须额外用两个布尔变量先把第一行和第一列原始状态备份下来。这一步就是所有错误提交的万恶之源。3.2 完整可提交的 O(1) 空间代码先给一版可以直接提交的 Python 实现每一行注释都对应一个关键步骤class Solution: def setZeroes(self, matrix: List[List[int]]) - None: m, n len(matrix), len(matrix[0]) # 备份第一行、第一列原始是否有 0 row0_has_zero any(matrix[0][j] 0 for j in range(n)) col0_has_zero any(matrix[i][0] 0 for i in range(m)) # 用第一行、第一列做公告栏 # 注意从 (1,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 # 根据公告栏修改内部区域 # 同样从 (1,1) 开始先把中间处理好 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] 0C 版本同样给出面试时用 C 写也是常见要求class Solution { public: void setZeroes(vectorvectorint matrix) { int m matrix.size(), n matrix[0].size(); bool row0 false, col0 false; for (int j 0; j n; j) { if (matrix[0][j] 0) { row0 true; break; } } for (int i 0; i m; i) { if (matrix[i][0] 0) { col0 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 (row0) { for (int j 0; j n; j) matrix[0][j] 0; } if (col0) { for (int i 0; i m; i) matrix[i][0] 0; } } };代码不算长但四个阶段的顺序一个都不能错备份、标记、处理内部、还原边缘。3.3 为什么必须额外记录 row0 和 col0很多人看代码时会疑惑第一行第一列不是已经被当成公告栏了吗为什么还要两个 bool 变量直接看反例最直观。考虑一个矩阵[[0, 2, 3], [4, 5, 6], [7, 8, 9]]唯一的 0 在 matrix[0][0]那么第 0 行和第 0 列都应该被置零。预期结果是[[0, 0, 0], [0, 5, 6], [0, 8, 9]]如果不备份 row0 和 col0只靠公告栏那么矩阵里唯一的 0 就落在公告栏本身它不会再去触发任何内部元素的标记。于是标记阶段结束公告栏上干干净净第二遍处理内部时什么都不做最终结果变成[[0, 2, 3], [0, 5, 6], [0, 8, 9]]matrix[0][1] 和 matrix[0][2] 没有被清零第一行明显错了。这正是因为 matrix[0][0] 的“自身是数据”含义和“自己是公告栏”含义叠在一起时必须单独把它拆出来记一遍。反过来说如果第一行本身有 0 但不在第一列比如[[1, 0, 3], [4, 5, 6]]第 0 行有 0所以整行要清零。但标记阶段只会记录 matrix[0][1] 对应第 1 列需要清零第一行自身是否清零这件事没有任何标记会触发。如果不备份 row0最终第一行会保留成 [1, 0, 3] 而不是 [0, 0, 0]同样是错的。所以这两个变量一个都不能省。3.4 处理顺序决定成败这个解法里顺序不是习惯问题而是正确性问题。第一阶段必须先备份第一行第一列的状态因为后面的标记阶段会往这两个位置写入 0等到最后想恢复时原始状态已经丢了。第二阶段只能从 (1,1) 开始扫描不能从 (0,0) 开始。因为公告栏上的 marker 本身也是矩阵元素如果把第一行和第一列当成普通数据参与扫描公告栏上的 0 会被当成“真实存在的 0”导致原本不需要清零的行列被误判。举例来说矩阵如果是[[1, 2, 3], [4, 0, 6], [7, 8, 9]]预期结果是[[1, 0, 3], [0, 0, 0], [7, 0, 9]]标记阶段正确执行后matrix[1][0] 和 matrix[0][2] 会被写成 0。如果第三阶段从 (0,0) 开始重新扫描看到 matrix[0][2] 0 会以为第一行有真实的 0于是把第一行整行清零最终得到错误的 [[0,0,0],[0,0,0],[7,0,9]]。这就是公告栏信号和数据混淆的典型事故。第三阶段处理内部区域也必须先从 (1,1) 开始并且第三阶段不能修改第一行第一列。原因超级简单内部的每个格子要判定自己是否需要置零依据就是公告栏上的标记如果你在第三阶段提前把公告栏清了后面的格子就没有参照物了。最后阶段才能还原第一行第一列。此时内部已经全部处理完公告栏变成废纸一张怎么改都不影响结果。4. 实操中一定会踩的坑4.1 反例一没备份第一行/第一列的状态把 3.3 里的反例浓缩成一句话如果矩阵的第 (0,0) 位置是 0不备份就一定会丢状态。我在实际提交记录里看到过不少版本把 row0 和 col0 的检查放在标记阶段之后结果就是整个矩阵正确率靠运气。还有一个衍生错误是备份时只备份一行或一列忘了另一个。比如只检查了第一行没检查第一列结果第一列原本有 0 时整个第一列不会被清零。一行代码的缺失会导致测试用例里凡是第一列有 0 的样例全部挂掉。提示备份阶段一定用两个独立变量一个管行、一个管列不要图省事合并成一个。4.2 反例二从 (0,0) 开始扫描标记这个坑我见过不止一次。代码写出来逻辑很像“扫描所有元素遇到 0 就在公告栏标记”于是循环范围写成 from 0 to m-1、from 0 to n-1。看起来覆盖面更广实际上一旦第一行或第一列本身有 0公告栏就会混入真实数据信号后续处理会产生连锁误判。正确的做法是 (1,1) 到 (m-1,n-1)把第一行第一列隔离在外。它们的信息已经通过 row0 和 col0 单独保存了不需要再进入主扫描。4.3 反例三边界尺寸和全 0 矩阵边界条件也是错误高发区。m 或 n 等于 1 时矩阵退化成一维。比如[[0, 1]]预期是把这一个 0 所在的行和列都置零得到 [[0,0]]。用标准解法走一遍row0 为 truecol0 为 true内部区域为空最后 row0 和 col0 处理完成后结果是 [[0,0]]正确。再比如[[1, 1], [1, 0]]只有一个 0 在右下角预期结果应该是[[1, 0], [0, 0]]用代码跑一次也能通过。这类单行单列矩阵最怕的其实是数组下标越界比如在 n0 时访问 matrix[0][0]。好在 Leetcode 现在限制 m、n 至少为 1但如果面试官把矩阵尺寸改成可能为 0就需要在前面加一个空矩阵判断。全 0 矩阵是好消息也是陷阱。说好是因为任何正确代码都能输出全 0说陷阱是因为如果你在本地用全 0 用例调代码几乎所有错误版本都能“恰好通过”根本测不出问题。所以自测时必须补一个“只有一个 0 在角落”的用例那才是考验备份逻辑的场景。4.4 纸上模拟一次完整流程用一个中等矩阵手工走一遍顺序感会更清晰。假设输入是[1, 2, 3] [4, 0, 6] [7, 8, 9]第一步检查第一行没有 0所以 row0False检查第一列没有 0col0False。第二步从 (1,1) 开始扫描(1,1) 的 4 不是 0(1,2) 的 0 出现于是标记 matrix[1][0]0、matrix[0][2]0。公告栏状态变为[1, 2, 0] [0, 0, 6] [7, 8, 9]第三步根据公告栏修改内部(1,1) 的判定条件是 matrix[1][0]0成立所以置 0(1,2) 同理置 0(2,1) 的判定条件是 matrix[2][0]0 或 matrix[0][1]0两者都是假所以保留 8(2,2) 的 matrix[0][2]0成立所以置 0。得到[1, 2, 0] [0, 0, 0] [7, 8, 0]第四步 row0 和 col0 都是 False第一行第一列不动。最终结果是[1, 0, 3] [0, 0, 0] [7, 0, 9]与预期完全一致。注意第二步矩阵中间那个 0 的位置原本是 6但在第三步被正确清零了。公告栏传递信息的过程在这个模拟里看得非常清楚。5. 延伸思考和它同类的算法题5.1 “只遍历一次”真的可能吗很多人看完 O(1) 解法会问能不能只遍历一遍就搞定答案是做不到。原因是矩阵置零的问题本质是一个“全局决策”问题第 (i,j) 个位置最终是否为 0取决于整个矩阵里是否存在某个 0 与它同行或同列。当你第一次扫到 (i,j) 时矩阵后半部分还没看你不可能知道它后面会不会蹦出一个 0 来决定它的命运。所以任何单遍扫描算法都需要在扫描过程中把“信息”存到某个地方而存信息的地方要么是额外数组要么是已经扫过的原矩阵区域。我们上面的 O(1) 方案实际上就是这种思路一边扫一边把信息写进公告栏第二遍再根据公告栏做最终修改。所以最优复杂度是两遍扫描这不是偷懒而是信息论层面的下限。5.2 矩阵操作类的同源题目矩阵置零的“用矩阵自身存状态”思路和几道经典题是互通的。第一道是 Leetcode 48 旋转图像。原地旋转矩阵时四个元素一组进行轮换面临的也是“被覆盖后信息丢失”的问题所以必须用临时变量暂存一个值。这和置零题里备份 row0 的逻辑如出一辙。第二道是 Leetcode 289 生命游戏。整个棋盘需要同时更新更新规则依赖每个格子的旧状态。如果你直接从左上角开始改后面格子拿到的是新状态结果就全错了。经典解法是引入中间状态值比如用 2 表示“原来是 0、新状态是 1”用 3 表示“原来是 1、新状态是 0”最后再统一转化。这本质上也是在原数组里编码“旧状态新状态”的双重信息。第三道是原地哈希系列比如 Leetcode 41 缺失的第一个正数、Leetcode 442 数组中重复的数据。这些题用数组下标当哈希桶用符号替代布尔标记核心逻辑同样是“在原数据内部做标记”。如果你能真正吃透矩阵置零再刷这几道题会有一种打通经脉的感觉。5.3 常见追问题汇总面试官拿到这道题后常见的追问大概有几种。第一种是“空间还能再省吗”直接把话题引向 O(1) 解法。第二种是“第一行第一列本身有 0 怎么办”考察你对信息覆盖的理解。第三种是“能否只遍历一次”就是 5.1 里的问题。第四种是“如何保证不误伤没有 0 的行列”考察对公告栏标记语义的理解。还有一些偏开放的追问比如“如果矩阵非常大一行放不下内存怎么办”。这种场景通常考虑按块读取或者用稀疏方式存储 0 的位置但已经超出 Leetcode 考察范围了。能说出“稀疏场景下记录 0 的位置列表可能比 O(1) 扫描更省”这种话会显得你有工程感觉。6. 刷题和面试的实战建议6.1 周赛限时环境下怎么写不丢分矩阵置零在周赛里属于签名题很多人一分钟就能写完但每次周赛的提交错误率并不低。问题基本都出在“想当然”三个字上。限时环境下最稳的做法是背住一个固定套路按顺序写四块代码备份、标记、内部处理、边缘还原。写完后再用脑子跑两组用例一组是角落有 0一组是第一行有 0 但第一列没有。我在 Leetcode 周赛里观察到错误代码的典型特征是只写了标记和还原省略了备份或者把扫描起点写成了 0。遇到这种题别追求炫技直接写最稳的 O(1) 模板就好。时间上花不到三分钟剩下的时间留给后面的题。6.2 面试作答的最优策略面试时不要一上来就写最优解那样反而显得像背答案。更好的节奏是先口述复制矩阵的朴素思路承认它空间不够好然后给出 O(mn) 的标记数组方案并说明为什么需要两遍扫描最后再抛出“能不能用第一行第一列当标记”的想法现场推导出 O(1) 解法。这个递进过程本身就是面试官想看的思维路径。每一层都基于上一层的不足做优化显得有逻辑而不是背模板。如果直接在白板上写 O(1) 解法面试官大概率会追问代码里的每个细节这时候你能把 row0、col0 的备份原理讲透反而更容易拿到高分。我自己的经验是在写代码前先用一句话跟面试官对齐思路“我把第一行当列标记把第一列当行标记然后单独处理第一行第一列自身的 0。”这句话一说面试官就知道你不是在默写代码。6.3 建议的自测用例清单刷题和真实面试里自测用例越全越稳。下面这份清单基本能覆盖所有边界用例类型输入示例检查重点全 0 矩阵[[0,0],[0,0]]输出仍为全 0不越界无 0 矩阵[[1,2],[3,4]]完全不变单元素矩阵[[0]]行列都处理不越界单行矩阵[[0,1]]整行清零单列矩阵[[1],[0]]整列清零角落有 0[[0,1],[1,1]]第一行第一列清零右下角保留第一行有 0 且第一列无 0[[1,0],[1,1]]第一行全清右列不动多个 0 重叠[[0,1],[1,0]]行列交叉结果正确这些用例不用全跑但写完后至少挑角落、单行、首行有 0 这三个重点验证就能把绝大多数 bug 挡在提交前。最后再分享一个我自己的小习惯每次写完这题后我会在注释里把四个阶段标上“备份”“标记”“内部处理”“边缘还原”四个词。这看起来很多余但确实帮我在面试紧张状态下保持清醒不至于手一滑就把顺序写乱。Leetcode 73 是个小题目但它的优化路径和结构意识能迁移到非常多后续题目里值得花时间认真写几遍。