到O(1)空间的原地标记算法详解)
1. 题目理解与核心思路拆解1.1 题目到底在问什么矩阵置零是力扣热题100里的经典题编号73在Hot 100里属于矩阵专题的基础题型。题目本身描述很简短给定一个 m x n 的矩阵如果某个元素是 0就把这个元素所在的行和列上所有元素都改成 0。举个例子输入一个 3x3 矩阵 [[1,1,1],[1,0,1],[1,1,1]]因为中间位置是 0所以最后要变成 [[1,0,1],[0,0,0],[1,0,1]]。很多第一次刷到这道题的人会觉得这太简单了——两层循环遍历遇到 0 就整行整列置零完事。但真正动手写才会发现坑不少你要是边遍历边改后面遍历到的 0 很可能就是刚才被改出来的最后整个矩阵全是 0直接翻车。这道题真正的考点不在怎么置零而在怎么优雅地记录哪些行哪些列需要置零以及如何把额外的空间开销压到最低。它考验的是对标记思想、状态记录和原地算法的理解这也是为什么它能被选进 Hot 100 的原因——题目短、解法多、坑深适合作为面试题反复考察。1.2 为什么这道题值得进Hot 100Hot 100 是整个力扣题库里被点踩率最低、面试出场率最高的一批题矩阵置零能进这个名单不是因为它算法多高深而是因为它特别适合作为面试考察题。它的考察维度很精准候选人能不能从最直观的解法出发一步步优化到空间 O(1)这中间体现的是对算法复杂度本质的理解而不是背题。另一个原因是这道题在矩阵操作题里具备很强的承上启下作用。它的标记思想在后续很多题里都会用到像生命游戏里原地记录状态、旋转图像里原地转置拿矩阵置零做基础训练后面刷这些题会顺很多。很多刷题攻略里也把这道题放在矩阵专题的开头就是这个原因。从实际面试角度看这道题还有一个好处即使候选人空间优化做不出来把 O(mn) 的解法写出来代码清晰、思路正确面试官通常也认可。它给了一个保底分同时又给进阶分留了空间是非常标准的面试友好型题目。1.3 先写一版能过但不够好的解法很多人的第一反应是先遍历整个矩阵把所有为 0 的位置记录到一个列表里比如记下坐标 (i, j)等遍历完之后再遍历这个列表把对应的每一行每一列置零。这确实能过代码也很简单def setZeroes(matrix): m, n len(matrix), len(matrix[0]) zeros [] for i in range(m): for j in range(n): if matrix[i][j] 0: zeros.append((i, j)) for i, j in zeros: for x in range(m): matrix[x][j] 0 for y in range(n): matrix[i][y] 0这个解法的时间复杂度是 O(mnk)其中 k 是 0 的个数因为每遇到一个 0 都要把整行整列重写一遍。更关键的是它占用了额外的 O(k) 空间来存坐标点如果矩阵特别稀疏k 接近 mn那这个额外空间开销就非常夸张最坏情况直接 O(mn)。所以这版代码虽然能过题但面试时要拿高分必须继续往下走。2. 解法演进从O(mn)到O(1)空间的思考路径2.1 方案一布尔数组标记法从上面粗暴方案开始优化最容易想到的是不用坐标点列表而是用两个布尔数组——一个长度为 m 的数组标记哪些行需要置零一个长度为 n 的数组标记哪些列需要置零。先遍历一遍矩阵遇到 0 就把 row[i] 和 col[j] 都标记为 True遍历结束后再根据 row 和 col 数组去把所有需要置零的位置改掉。def setZeroes(matrix): m, n len(matrix), len(matrix[0]) row [False] * m col [False] * n for i in range(m): for j in range(n): if matrix[i][j] 0: row[i] True col[j] True for i in range(m): for j in range(n): if row[i] or col[j]: matrix[i][j] 0这个方案的时间复杂度是 O(m*n)空间复杂度是 O(mn)。相比第一种方案它不管矩阵里有多少个 0额外空间都是固定的 mn不会因为 0 的数量变多而膨胀而且代码结构也更清晰。这是面试里绝大多数人能想到的解法也是大多数参考答案给出的标准解法。但这个方案还有优化空间。空间 O(mn) 虽然不大但面试官通常会追问一句能不能做到 O(1) 空间如果你在这个问题上卡住了那这道题就只能算会做一半。O(1) 空间才是这道题真正的分水岭。2.2 方案二原地标记法最推荐O(1) 空间的做法核心思路是把标记信息直接存到矩阵自身的第 0 行和第 0 列里。既然我们最后要置零一整行一整列那每一行每一列的状态至少需要一个比特位来记但题目不让用额外数组那最自然的做法就是借用在遍历中不会被提前误伤的位置来存这些标记。具体来说先用第 0 行的每一个格子来标记对应列是否需要置零用第 0 列的每一个格子标记对应行是否需要置零。比如 matrix[2][0] 标记第 2 行是否要置零matrix[0][3] 标记第 3 列是否要置零。遍历所有格子时如果发现 matrix[i][j] 0就同时把 matrix[i][0] 和 matrix[0][j] 标记为 0这个用 0 表示需要置零的设计非常巧妙因为最后要给这些行置零时你的操作本身就是赋 0不会产生额外开销。这里有个关键细节第 0 行和第 0 列本身是否包含 0这个信息会被标记过程覆盖掉。所以第一步得先单独记录一下第一行和第一列原本有没有 0保存到两个布尔变量里。等所有标记和回填完成之后再单独处理第一行和第一列。2.3 为什么从后往前更优雅上面说的原地标记法实现时有一个非常经典的写法差异处理标记回填的顺序。很多人第一版写出来是这样的def setZeroes(matrix): m, n len(matrix), len(matrix[0]) first_row any(v 0 for v in matrix[0]) first_col any(matrix[i][0] 0 for i in range(m)) 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: for j in range(n): matrix[0][j] 0 if first_col: for i in range(m): matrix[i][0] 0这个写法已经可以 AC 了先记录第一行第一列的原始状态再用它们做标记最后单独处理第一行第一列。但很多人会觉得这段代码有点啰嗦而且两个布尔变量的使用也容易出错。更经典的写法是从后往前遍历。思路是这样既然第 0 行和第 0 列是标记区那就先别动它们从最后一行往前处理数据区处理完数据区再处理第 0 行和第 0 列。这样就不需要加 first_row 和 first_col 两个变量了因为第 0 行第 0 列本身的原始状态不会在标记阶段被破坏。具体实现就是先从最后一行往上遍历用 matrix[0][j] 和 matrix[i][0] 作为标记位遇到 0 就把对应标记位设为 0然后再从最后一行往上回填遇到标记为 0 的行或列就置零整个当前位置最后再单独处理第一行和第一列。这样代码更短逻辑也更顺是 LeetCode 官方解法的推荐写法。3. 实现细节与边界处理3.1 第一步记录第一行第一列的原始状态如果采用从后往前的写法处理顺序就得重新安排。第一步不是去记录状态而是要先把第 0 行和第 0 列本身是否为 0 的信息保留下来防止下一步标记阶段把原始信息覆盖掉。最简单直接的办法就是用两个布尔变量去记录不过用完后需要立刻单独处理掉。def setZeroes(matrix): m, n len(matrix), len(matrix[0]) first_row_has_zero any(matrix[0][j] 0 for j in range(n)) first_col_has_zero any(matrix[i][0] 0 for i in range(m))有的刷题攻略里会用从后往前遍历来省去这两个布尔变量写法是用第 0 行和第 0 列做标记但在第一次遍历时跳过第 0 行和第 0 列先遍历数据区第二次遍历时从最后一行往第 1 行回填同时检查第 0 列第三次遍历时从最后一列往第 1 列回填同时检查第 0 行。这种做法可以把代码压缩到十几行但说实话面试时写得太压缩不一定加分反而更容易在边界处理上出错。我更建议用一个标志变量把第一行第一列的原始状态存下来代码清晰也不容易漏。3.2 第二步用标记位记录哪些行/列要置零标记阶段是整个算法的核心也是最容易想当然写错的地方。正确思路是遍历矩阵中除第 0 行和第 0 列以外的所有格子如果发现某个格子的值为 0就把它所在行的开头格 matrix[i][0] 设为 0以及所在列的开头格 matrix[0][j] 设为 0这两个位置就充当该行需要置零和该列需要置零的标记。为什么这么设计因为一个格子的值只可能被两种情况影响它所在的行需要置零或者它所在的列需要置零。如果用标记位把这两种状态记录下来那么回填阶段只需要检查矩阵[i][0]和矩阵[0][j]就能知道当前位置要不要赋 0。整个过程不会使用任何额外空间标记本身也是 0 值不影响后续赋值操作。这里有一个很多人踩过的坑在标记阶段遍历数据区的时候如果遇到矩阵[i][0]的值为 0这个 0 本身也需要被正确处理。也就是说标记阶段遍历的是整个矩阵包括第 1 行到第 m-1 行、第 1 列到第 n-1 列而不是跳过边界列。一旦在标记阶段把矩阵[i][0]改成了 0这个0也要作为信号传递到对应的列标记里。3.3 第三步按标记回填矩阵回填阶段相对简单就是再遍历一遍整个数据区第 1 行到第 m-1 行、第 1 列到第 n-1 列如果当前格子的行标记或者列标记是 0就直接把当前格子赋为 0。这里用或运算判断即可因为不管行要置零还是列要置零结果都是当前格子变成 0。回填阶段最需要注意的是遍历顺序。很多人会习惯从第 0 行往最后一行遍历但这样会有一个隐患假设第一行的某个格子本身不是 0但因为某列标记为 0 被置零了你再遍历到这一行后面的格子时会发现 matrix[i][0] 已经被改成 0于是误以为是行标记导致还没检查到标记位就已经把状态污染了。所以正规做法是从最后一行往回走从最后一行开始处理这样就永远先处理数据区最新的标记不会破坏尚未使用的标记信息。我自己刷这道题时的经验是写回填的时候循环变量 i 和 j 都从 m-1 和 n-1 倒着走。这样写可以有效规避很多边界问题代码也更安全。3.4 代码实现与逐步解读把上面几个步骤串起来完整代码就这样def setZeroes(matrix): m, n len(matrix), len(matrix[0]) first_row_has_zero False first_col_has_zero False # 记录第一行和第一列是否有0 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这段代码的时间复杂度是 O(m*n)空间复杂度是 O(1)完美符合题目进阶要求。中间几个 for 循环单独看都非常简单但组合起来就体现了一个完整的标记-回填流程面试时能一口气写出来基本就能拿满这道题的分数了。4. 常见错误、调试心得与面试技巧4.1 高频易错点排查表矩阵置零这道题虽然代码不长但错误率出奇地高。我自己刷题和帮朋友 review 代码的时候总结出几个最高频的错误点这里整理成一张表方便大家对照自查错误类型具体表现根本原因标记覆盖第一行第一列的原始 0 被标记覆盖导致后续处理漏掉没有在标记前用变量记录第一行第一列的原始状态遍历顺序错误从前往后回填导致后面的行被前面的置零操作误伤没有理解标记信息会被回填过程破坏的原理只标记行不标记列遇到 0 只把所在行加了标记漏掉所在列的标记没有意识到同一个 0 同时影响行和列重复置零对已经置零过的位置再次赋 0虽然没有逻辑错误但时间浪费回填阶段没有用条件判断而是无条件赋 0边界判断遗漏m1 或 n1 时循环边界写错直接数组越界没有针对特殊形状的矩阵单独测试这些错误里最致命的是标记覆盖和遍历顺序错误因为这两个会导致结果完全错误而且不仔细看根本察觉不到。很多人在 LeetCode 上提交后看到 Wrong Answer检查半天最后发现是自己把第一行的标记覆盖了这种情况我在面试时见过不止一次。4.2 我在面试中踩过的坑这道题我面试别人时特别喜欢问因为它太容易看出一个人的代码功底了。我记得有一次面试一位候选人他很快写出了 O(mn) 的解法思路完全正确代码也规范但当我追问能不能 O(1) 空间时他的第一反应是应该不能吧已经最优了然后就开始犹豫最后在我的提示下才想到了原地标记。这个场景其实很能说明问题很多人会写代码但对还能不能更好这件事缺乏主动思考。面试官问这道题并不是真的关心矩阵里 0 的处理而是想看候选人有没有主动优化空间复杂度的意识。所以刷这道题的时候建议把三种解法暴力坐标法、布尔数组法、原地标记法都写一遍并且把每种的复杂度都算清楚面试时才能应对追问。我还遇到过一种情况候选人用 Java 写的时候在标记阶段直接遍历整个矩阵而不是跳过第一行第一列结果把第一行第一列的标记位也清零了然后后面回填的时候所有格子全被置零。这个错误非常隐蔽因为单看某个位置好像没问题但整体结果就错了。排查这种错误的最好办法是在本地多跑几个测试用例尤其是包含多行多列、多个 0 的用例。4.3 测试用例怎么设计算法题写完之后测试用例的设计也是体现专业度的地方。很多人刷题只跑一遍示例就提交了这样很容易漏掉边界情况。针对矩阵置零我建议至少覆盖以下几类用例第一类是题目给的示例比如 [[1,1,1],[1,0,1],[1,1,1]]验证基本功能。第二类是矩阵第一行就有 0 的情况比如 [[0,1,1],[1,1,1],[1,1,1]]检验对第一行原始状态的保留和最后处理是否正确。第三类是矩阵第一列就有 0 的情况。第四类是单行或单列矩阵比如 [[1,0,1]] 或 [[1],[0],[1]]这类极端形状最容易暴露循环边界问题。第五类是全 0 矩阵以及完全没有 0 的矩阵前者检验重复置零是否冗余后者检验无标记时的行为。我在本地测试的时候一般会写一个简单的断言函数把输入矩阵和输出矩阵都打印出来对比这样出错时能第一时间定位。LeetCode 的题目本身没有让输出但本地排错时打印矩阵非常方便强烈建议养成这个习惯。5. 刷题策略Hot 100的正确打开方式5.1 矩阵操作题怎么串着刷矩阵置零不是一道孤立的题它在 Hot 100 里属于矩阵操作专题和旋转图像、螺旋矩阵、生命游戏这些题经常一起被推荐。刷题攻略里通常会说先刷矩阵置零再刷旋转图像然后刷螺旋矩阵最后刷生命游戏。这个顺序是有道理的。矩阵置零引入的是原地标记思想也就是如何在不申请额外空间的情况下用数据结构自身来存储状态。生命周期里的原地标记比这更进一步要求你用 2 个 bit 同时记录当前状态和下一状态这类题目打基础时最需要的就是矩阵置零这种温和的训练。如果你按这个顺序刷会发现它们之间有很强的递进关系矩阵置零是标记然后用标记回填旋转图像是先转置再逐行反转螺旋矩阵则是模拟遍历顺序。每道题都在前一道题的基础上加了一点新东西刷完整个专题你对矩阵操作的掌握就会有一个质的提升。5.2 题目变形与考题进化矩阵置零还有几个常见的变形面试时可能会换个方式考。比如输入不是普通矩阵而是链表矩阵或者要求你返回的不是最终矩阵而是记录哪些行哪些列需要置零的布尔值。还有的变形题会把矩阵里的 0 换成其他特殊值比如 -1其他数字可以正常操作只有遇到 -1 才需要置零。其中最常见的一种变形是给定一个 m x n 的矩阵如果某个位置的值是目标值 t就把该位置所在的行和列都变成 t。这种题其实就是矩阵置零的原地标记法直接换皮只要掌握了标记-回填的思路无论目标值是什么操作逻辑完全一致。另外一个面试中经常出现的追问是如果矩阵是一个稀疏矩阵你要怎么优化这个问题考的是对数据结构的理解。稀疏矩阵通常用三元组或压缩列存储来表示在这种情况下矩阵置零的解法可能会变成先收集所有非零位置再逐个处理思路和坐标点列表法接近但空间效率更高。能回答出这个层面的候选人在算法和数据结构方面通常能拿到加分。5.3 刷题顺序建议如果你刚开始刷力扣 Hot 100我的建议是不要按题号顺序刷而是按标签和难度分组刷。矩阵置零属于数组/矩阵专题和它同组的推荐题目包括最大子数组和、合并区间、轮转数组、除自身以外数组的乘积、螺旋矩阵、旋转图像。先把这些题一起刷完你对数组操作的理解会非常扎实。从难度梯度来看矩阵置零本身是中等难度的题目适合作为数组专题的中期练习题。建议顺序是先做简单题热身比如两数之和、合并两个有序数组然后进入中等题阶段优先做矩阵置零这种思路直观但需要优化的题最后再去碰困难题比如接雨水、滑动窗口最大值。这样循序渐进不会一开始就被劝退。另外提一嘴矩阵置零这道题在 LeetCode 上有一个很有意思的现象通过率很低但一旦你理解了原地标记的思想后你会发现它其实非常简单。通过率低不是因为它难而是因为它考察的是很多人忽视的空间复杂度优化只要你刷题时多问自己一句能不能不用额外空间这道题的核心考点就已经被你击破了。
