矩阵置零原地修改：从O(mn)暴力到O(1)空间解法

矩阵置零这道题，我第一次在线上刷到的时候，觉得它顶多算个中档送分题：遍历一遍，遇到0就把行列改了呗。结果提交之后连续踩了好几个测试用例，才意识到“原地修改”四个字到底有多容易让人翻车。后来我把这道题的暴力复制法、标记数组法，以及真正的O(1)空间解法都完整过了一遍，又把边界条件挨个测了一遍，才敢说这个题值得好好拆一遍。这篇文章就按我自己的思考顺序和踩坑顺序来写，适合正在准备技术面试、想搞懂原地算法套路、或者想在矩阵类题目上建立一点直觉的读者。

1. 第一次做这道题，我的暴力解法是怎么翻车的

1.1 先把输入输出边界说清楚

矩阵置零的输入是一个m行n列的二维数组，数组元素是整数。规则是：任意一个格子为0，它所在的整行和整列最终都必须被改成0。注意两个细节：第一，一个0只影响它自己所在的行和列，不会斜向扩散；第二，题目要求直接修改原数组，函数签名通常不返回新数组。换句话说，你不能新建一个矩阵算好再返回，必须在传入的matrix对象上原地改。

这个前置条件很关键。很多第一次接触这道题的人，包括我自己，第一反应都是复制一份原矩阵作为判断依据。复制本身不是不行，但它会直接把这道题的空间复杂度拉满，这也是后面所有优化方案要解决的问题。

1.2 复制矩阵的做法，和它真正的问题

第一版代码我写得很直白：

def set_zeroes_v1(matrix): m, n = len(matrix), len(matrix[0]) backup = [row[:] for row in matrix] for i in range(m): for j in range(n): if backup[i][j] == 0: for k in range(n): matrix[i][k] = 0 for k in range(m): matrix[k][j] = 0

遍历备份矩阵，遇到0就去原矩阵把对应行和列全部清零。因为判断依据来自副本，所以无论原矩阵怎么改，都不会影响后续判断。这个方案的正确性没有悬念，但空间直接用了O(mn)，时间在最坏情况下还会因每个0都各触发一轮清理而变得更高。面试官看到这个版本，通常会微笑着问一句：能不能不要复制整个矩阵？我第一次被问到这个问题时，其实已经想到了“改完就回不去”的矛盾，但一时没有找到一个干净的落地方式。这恰恰是这道题最有价值的思考点。

1.3 边遍历边改，为什么一定出错

我当年也试过直接在原矩阵上遍历：遇到matrix[i][j]为0，马上把第i行和第j列改成0。听起来更快，但用一个最简单的例子就能让这个方案暴露问题。

矩阵[[1,0],[2,3]]，正确答案是[[0,0],[2,0]]。如果边遍历边改，先看到的是matrix[0][1]等于0，于是把第0行和第1列全改成0，矩阵变成[[0,0],[2,0]]。继续往后遍历，下一个格子matrix[1][1]现在已经是0了——这个0并不是输入数据里的原始0，而是刚刚被制造出来的。程序无法区分二者，于是又认为第1行需要清零，把矩阵改成了[[0,0],[0,0]]。这就是典型的“污染”问题。

所以“记录零的位置”和“把整行整列清零”必须拆成两步。判断依据必须在第一步完整收集好，第二步只管执行，不再做任何实时判断。这个原则看起来简单，却是整道题几乎所有正确解法的共同地基。

1.4 暴力解法告诉我的两个结论

回头看，暴力解法的价值不在于它能提交通过，而在于它逼我回答了三个问题：

• 需要保存的信息到底是什么？答：某行是否含0、某列是否含0，而不是所有0的具体坐标。
• 为什么不能一遍扫完？答：因为新产生的0会污染后续判断。
• 最小需要多少额外空间？答：取决于信息存储方式，最省可以做到常量级。

带着这三个答案，后面两条优化路径就非常自然了。

2. 用标记数组省空间：从O(mn)到O(m+n)的关键一步

2.1 信息粒度压缩：从零的坐标到行列标志位

第一版的痛点在于复制了整张矩阵。仔细想想，真正决定输出结果的信息，其实只包含“哪几行有0”和“哪几列有0”。0在那一行的哪一列出现，完全不重要；只要这一行出现过0，整行最终都会被清空。所以可以用两个数组来存这个信息：行长度的布尔数组记录行的状态，列长度的布尔数组记录列的状态。这样无论矩阵多大，额外空间都只是行数加列数，也就是O(m+n)。

这一步优化的本质，是把信息粒度从“每个零的位置”压缩到“行和列的拥有关系”。如果某个矩阵是10000行、10000列，但只有三个0，那三个坐标当然也可以存；可如果0的数量很多，坐标数组会膨胀到O(mn)。布尔数组的长度和行列数绑定，是最坏情况下也能保证的稳定方案。

2.2 两趟遍历各管一段的代码

代码只需要两个循环阶段。

def set_zeroes_v2(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

第一趟只做一件事情：把0的出现映射成行标志和列标志。第二趟只做一件事情：按标志把对应的格子清零。代码本身没什么可发挥的空间，但实现里最常犯的错误，是有人试图把这两趟合并成一趟，在标记的同时直接改矩阵。这又回到了污染问题：前面格子被清出的0，会让后面的rows和cols标志被错误地置位。

2.3 为什么“收集零坐标列表”不是更好的选择

写到这里，有人可能会问：那我第一趟把所有为零的坐标存进一个列表，第二趟再遍历这个列表，把每个坐标对应的行和列处理一遍，不也一样吗？对，但空间复杂度在最坏情况下会退化。当矩阵里几乎全是0时，这个坐标列表的长度接近m乘n，额外空间又回到了O(mn)。虽然大部分面试场景能凑合，但既然题目明确考察的就是空间优化，用布尔数组才是更标准的答案。

另外还有个实现细节值得注意：如果第二趟用条件“rows[i] or cols[j]”判断，最终效果是行和列取并集。这样不会重复计算，也不会漏掉某个格子。有的解法会把两趟循环改成“先按行标志清理，再按列标志清理”，效果等价，但更容易写乱。所以我的建议是保持“判据统一”的两趟结构，逻辑最干净。

3. 真正O(1)的解法，藏在整个矩阵的第一行和第一列

3.1 让矩阵自己给自己当标记板

O(m+n)的解法已经很好了，但面试官大概率会继续追问：能不能连这两个数组都不要，直接用常量空间？答案是可以，方法就是借用矩阵自身的第一行和第一列。

具体做法是这样：第一列有m个格子，正好可以在每个格子上记录“这一行是否存在0”；第一行有n个格子，正好可以在每个格子上记录“这一列是否存在0”。换句话说，如果数据区里某个格子matrix[i][j]是0，我们就把matrix[i][0]改成0，再把matrix[0][j]改成0。这样，第一列变成了一个长度为m的行标志数组，第一行变成了一个长度为n的列标志数组。标记信息全部落在矩阵边框上，不再需要额外的两个数组。

这个过程很像开会时让前排观众当临时引导员，借用他们的座位存放临时的指示信息。但借座位有个前提：引导员本身还有自己的原信息，必须先把原信息妥善保存，否则散场后你根本不知道他原来坐哪。

3.2 两个布尔变量，是O(1)方案里必须保留的“小抽屉”

直接用第一行第一列做标记，马上会遇到一个覆盖问题：第一行自己也是矩阵的数据。如果第一行某个格子原本就是0，这个事实必须转成“第一行需要整行清零”的结论。但我们又会往第一行格子写列标记，两者共用同一个位置，存在冲突。同理，第一列也面临同样的冲突。

所以实现的第一步，不是急着标记，而是先顺次检查第一行和第一列，把“第一行原本是否有0”“第一列原本是否有0”分别记进两个布尔变量。这两个变量不随矩阵规模变化，因此整个算法的额外空间复杂度称为O(1)。这也是很多人容易理解偏的地方：O(1)不是说连一个变量都不用，而是说额外空间必须是常数级别。

3.3 执行顺序的完整演示

如果用文字把流程概括一遍，是这样的：

1. 判断矩阵是否为空。
2. 扫描第一行，记录firstRowZero。
3. 扫描第一列，记录firstColZero。
4. 从下标(1,1)开始扫描数据区，遇到0就把行列标记写到边框上。
5. 再次从下标(1,1)开始遍历数据区，根据边框标记把相应格子清零。
6. 最后处理第一行和第一列本身，根据两个布尔变量决定是否整行/整列清零。

第4步和第5步为什么都要严格从(1,1)开始，而不是整个矩阵？因为下标0这一行一列是标记板，它们要等到第6步才按最原始的布尔变量来决定最终值。如果中途把标记板当普通数据清掉，记录在板上的行列信息就会集体丢失。

3.4 一个完整例子的手工推演

拿一个3乘3的矩阵来看：

[[1, 2, 3], [4, 0, 5], [6, 7, 8]]

• 扫描第一行，三个数都不是0，firstRowZero为False。
• 扫描第一列，1、4、6也都不是0，firstColZero为False。
• 扫描数据区，(1,1)是0，于是matrix[1][0]和matrix[0][1]都被改成0。
• 第二遍从(1,1)开始：第1行的所有格子因为matrix[1][0]为0而被清零；第1列的所有格子因为matrix[0][1]为0而被清零；其他格子保持原值。
• 最后firstRowZero和firstColZero都是False，第一行第一列保持处理后的值。

得到：

[[1, 0, 3], [0, 0, 0], [6, 0, 8]]

手工核对原始矩阵，只有(1,1)一个0，那第1行和第1列全变成0就对了。特别留意一下最后一步的意义：matrix[1][0]因为“第1行有0”而变成0，但它同时也是第一列的元素，第一列最终确实应该全0，所以没有矛盾。matrix[2][0]属于第0列，第0列没有0，所以保持6，也正确。

4. 完整代码提交前，我踩过的边界坑和排错思路

4.1 最终版本的完整代码

把上面的步骤翻译成代码，长这样：

def set_zeroes(matrix): if not matrix or not matrix[0]: return m, n = len(matrix), len(matrix[0]) first_row_zero = False first_col_zero = False for j in range(n): if matrix[0][j] == 0: first_row_zero = True break for i in range(m): if matrix[i][0] == 0: first_col_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_zero: for j in range(n): matrix[0][j] = 0 if first_col_zero: for i in range(m): matrix[i][0] = 0

这段代码在大部分能跑通的测试用例上都没有问题。真正容易出错的，反而是看起来不太起眼的边界情况。

4.2 单行、单列、空矩阵

先看空矩阵。如果传入的是[]或者[[]]，直接return。很多题面会保证m和n不小于1，但写防御性判断成本很低，建议留着。

再看单行矩阵，比如[[1,0,2]]。firstRowZero会被置为True，数据区扫描的起始下标是(1,1)，而m等于1，所以两个循环都不会进入。最后firstRowZero为True，整行清零，结果是[[0,0,0]]，正确。如果这一行一个0都没有，firstRowZero为False，所有循环都不动任何值，结果保持原样，也正确。

单列矩阵的原理一模一样，只是角色互换。我有一次在单行矩阵的测试用例上卡了很久，原因是计数变量写错了，把range(1, m)写成了range(0, m)，结果数据区和边框都在处理，导致第一行被当成数据区提前清掉，后面的标记全部失效。这类问题的排查思路很简单：先固定输入只有一行，然后手动走一遍循环边界，基本一眼就能看出问题。

4.3 第一行或第一列本身有0时的正确性验证

这也是最容易让人发怵的场景。先看一个只有第一行有0、第一列没有0的例子：

[[2, 0], [3, 4]]

扫描得到firstRowZero为True，firstColZero为False。注意，matrix[0][1]本身是0，它同时自动充当了“第1列需要清零”的列标记，所以在第二遍遍历数据区时，(1,1)会因为matrix[0][1]为0而被清成0。最后阶段firstRowZero为True，第一行整行清零，结果变成：

[[0, 0], [3, 0]]

手工核对：原始0在(0,1)，第0行全0，第1列全0，matrix[1][0]属于第0列，第0列没有0，所以保持3，正确。

如果第一行第一列同时带0，比如[[0,1],[2,3]]，firstRowZero和firstColZero都是True。数据区没有0，标记阶段什么都不做，最后一步把第一行和第一列全部清零，结果[[0,0],[0,3]]。这符合题意，因为第0行和第0列确实都含0。

这里需要想清楚的逻辑是：第一行有0，只代表第一行这一行应该全0；它不代表第一列也应该全0，哪怕matrix[0][0]恰好是0。matrix[0][0]会跟着第一行一起变成0，但第一列的其他元素不受影响。把这个方向和维度的直觉理顺，就不会在处理边框时搞混。

4.4 我实际排错时用的测试用例清单

把代码写完，我一般会一次性喂这一组用例验证：

如果这些用例都过，基本可以放心提交。我自己的教训是：单纯依赖在线判题的测试用例远远不够，那些用例会覆盖边界，但因为报错信息不直观，定位反而更慢。先在本地把这些极端情况跑一遍，省下的时间远比写用例的时间多得多。

5. 面试官想从这道题里听到什么，以及它带来的工程启发

5.1 三个层次的解法，暴露的是三种思维方式

这道题之所以被反复使用，是因为它用一道题的梯度把一个人的基础分层分得很清楚。

• 能写出复制矩阵版本：说明对问题有基本理解，会写嵌套循环，但缺少空间敏感度。
• 能写出标记数组版本：说明知道用更少的信息表达同样的问题，具备常见的空间换时间判断力。
• 能写出O(1)版本：说明不仅会写代码，还能处理“信息覆盖”这类工程里常遇到的难题，并且对执行顺序有很强的掌控力。

面试官想听的往往不是最终答案，而是你在从第一层往第三层走的时候，能不能把“为什么不能直接改矩阵”“为什么第一行第一列需要提前保存”讲明白。这些思考过程比提交的代码更有说服力。

5.2 和它血缘很近的一批矩阵题

掌握了矩阵置零的套路，再看下面几类题会顺很多：

• 旋转图像：同样在二维数组上反复折腾下标，核心是四个顶点循环交换的顺序。
• 生命游戏：需要在原数组上保存“当前状态”和“下一状态”两种信息，常见的技巧是用中间状态值做占位，第二遍再归一化。
• 螺旋矩阵、对角线遍历：考验对行列边界的敏感度，矩阵置零里的“第一行第一列作标记板”思路对它们没直接帮助，但预处理、分步处理的思想是相通的。

如果展开说，生命游戏和矩阵置零尤其像：都是“原地修改”加上“状态可能互相覆盖”。生命游戏的常用解法是定义0到1用-1，1到0用2之类的编码，把新旧状态藏在同一个格子里，最后再统一刷新。这套思路和把行列标记藏在矩阵边框上，本质上是同一个抽象：状态不能丢，又不能占用新空间，那就借用原有的位置，玩好“编码、解码”的把戏。

5.3 从算法题联想到的工程实践

矩阵置零的“借用原空间”思路，放到真实系统里也有对应场景。比如图像处理时，经常需要在像素图上临时标注哪些点属于待处理区域；如果不想重新分配一整张标注图，就可以把特殊数值写进原图的某些通道位，处理完再统一还原。再比如数据清洗时，某一行某一列出现了一个非法值，清洗逻辑往往要把整行整列标记为不可信，这和矩阵置零的“0让整行整列失效”模型几乎一样。

这些场景的共同点是：信息必须记录下来，但内存不允许你随意扩张。此时最先要想清楚的就是覆盖问题：哪些位置的信息会被复用，复用前需不需要把原值抢救出来。矩阵置零用两个布尔变量解决了这个问题，这个经验可以说直接迁移到很多低资源环境下的编码方案里。

5.4 如果是我来作答，我会怎么组织表达

最后分享一个实战性的建议。在面试中拿到这类题，不要急着写代码，先把三种解法按复杂度从低到高列出来，说清楚各自的空间开销和关键风险。当对方让你选择一种来实现时，再问清楚是否需要原地修改。如果要求原地，直接写O(1)版本，写完后再用一两个输入快速走一遍流程，重点验证第一行第一列的标记步骤。

如果时间紧张，难免在现场把代码写乱，我的习惯是先在白纸上画出矩阵边框，标明哪些格子是行标记、哪些是列标记、两个布尔变量分别放在哪，然后再动手。这套“先把布局画清楚，再填充代码”的习惯，救过我很多次，尤其适合这种标记复用原空间的题目。

最后再分享一个小经验：做矩阵置零这题，最有价值的收获不是背下那段代码，而是记住“记录信息”和“落地修改”必须分阶段这个原则。我后来写很多原地修改的代码，都会先在注释里标清楚“第一阶段：收集信息”“第二阶段：应用信息”“第三阶段：还原被复用空间的原信息”，等三个阶段都想明白了，再往里面填代码。矩阵置零正好把这三个阶段压缩在一个极小的例子里，这也是它明明看起来简单，却值得反复琢磨的原因。