矩阵置零算法详解：从O(mn)空间到O(1)原地标记法-育师

矩阵置零这道题，我在面试别人和自己刷题的时候都见过太多次了。题目描述看第一眼都觉得简单得像送分题：一个 m x n 的矩阵，只要某个元素是 0，就把这一整行和这一整列全部变成 0。可真到了手写代码的环节，一半以上的人会栽在同一个地方——原地修改时出现了“连锁污染”，新置出来的 0 又被当成原始 0 继续扩散，最后整个矩阵全变成 0。

所以这篇文章不打算只给一个标准答案，我会把从 O(mn) 空间到 O(1) 空间的完整解法演进过程拆开讲清楚，包括为什么常规标记法可行、原地标记法又是怎么从里面推出来的、第 0 行和第 0 列凭什么能当“记录板”，以及我实际调试时踩过的几个边界坑。不管你是刚开始刷算法题的新手，还是准备大厂面试需要系统复盘的老手，这一篇都值得看完。

1. 先读懂题意：置零的“连锁污染”是唯一真正的难点

题目本身一句话就能说完：给定一个 m x n 的矩阵，如果某个元素为 0，则将其所在行和列的所有元素都置为 0。比如下面这个例子：

[[1, 1, 1], [1, 0, 1], [1, 1, 1]]

中间的 0 位于第 1 行第 1 列，所以第 1 行和第 1 列要整体变 0，结果就是：

[[1, 0, 1], [0, 0, 0], [1, 0, 1]]

再比如稍微复杂一点的：

[[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]

原矩阵里有 2 个 0，分别是 (0,0) 和 (0,3)。因为第 0 行存在 0，所以第 0 行整行变 0；第 0 列和第 3 列也整列变 0。最终结果是：

[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

麻烦的地方就在这里：一旦你把第 0 行整行置成 0，那么第 0 行上本来不是 0 的格子也会变成 0。如果此时还在继续遍历矩阵，把这些新出现的 0 也当作“原始 0”去处理，你又会把对应的行和列再置 0，于是连锁反应会把整张矩阵全部吞掉。

很多人第一直觉是“边遍历边改”，比如从左上角扫到右下角，遇到一个 0 就立刻把所在行和所在列全置 0。这种做法跑上面的第二个例子，结果往往直接变成一个全 0 矩阵。原因很简单：你分不清哪个 0 是原来就有的，哪个 0 是你刚才制造的。这道题表面上考的是矩阵遍历，实际上考的是“如何区分原始信息和中间产物”，或者说，如何保存状态。

从面试官的角度看，题目真正想考察的也不是你能否写出 for 循环，而是你能不能在做标记时避免自身信息的丢失，并且把空间复杂度压到常数级。理解了这一点，后面的解法演进就有了一条清晰的主线：先解决正确性问题，再解决空间效率问题。

2. 两条常规解法：拷贝矩阵与“行/列标记数组”的取舍

2.1 直观但耗内存的拷贝矩阵法

最容易想到的方案，也是我当年最早写出来的版本：先复制一份完整的矩阵出来，然后遍历原矩阵，找出所有 0 的位置，再回到原矩阵中把这些 0 所在的行和列全部置 0。

为什么拷贝一份就能避免连锁污染？因为在拷贝矩阵中找 0 的时候，不会有人去修改拷贝矩阵；原矩阵怎么改都行，反正判断依据来自另一个独立副本。等于是用空间换取了“信息隔离”。

代码思路大概是这样的：

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

这段代码正确性没问题，但时间复杂度其实是 O(mn*(m+n))，因为每遇到一个 0 就要立刻横向纵向扫一遍。复制矩阵本身要 O(mn) 的额外空间。如果矩阵规模一旦上去，比如 1000×1000，光是复制一份就要占据和原矩阵同样的内存，这在很多竞赛或工程场景下是不可接受的。

即使把拷贝矩阵法优化成“先记录所有 0 坐标，再统一置零”，也就是先扫描一遍拿到所有 (i,j) 零坐标，再针对每个坐标置零对应行列，避免了 m+n 的二次循环，但 O(mn) 的额外空间这个硬伤仍然存在。作为保底答案可以，但不该止步于此。

2.2 更好想的标记数组法：O(m+n) 空间

顺着“先记录位置，再统一处理”的思路往下走，大多数刷题的人会写出第二个版本：用两个一维布尔数组，一个标记哪些行需要置 0，一个标记哪些列需要置 0。

row_flags = [False] * m col_flags = [False] * n

第一遍遍历整个矩阵，如果发现 matrix[i][j] == 0，就把 row_flags[i] 和 col_flags[j] 置为 True。第二遍再遍历一遍，只要当前格子所在的行或列被标记过，就把它置为 0。

def set_zeroes_flags(matrix): m, n = len(matrix), len(matrix[0]) row_flags = [False] * m col_flags = [False] * n for i in range(m): for j in range(n): if matrix[i][j] == 0: row_flags[i] = True col_flags[j] = True for i in range(m): for j in range(n): if row_flags[i] or col_flags[j]: matrix[i][j] = 0

这个版本时间上是标准的 O(mn)，空间上是 O(m+n)。注意这里不再需要二维辅助数组，因为“需要置零的行集合”和“需要置零的列集合”各自只需要一维的信息。这也是大部分面试官能够接受的次优解。

但从优化角度看，m+n 的额外空间还不够极致。如果 m 和 n 都是 10^4 的规模，两个布尔数组加起来就是 20000 个 bool，虽然不算大，但题目进阶要求往往写的是“尽量使用 O(1) 的额外空间”。于是第三个版本，也就是常说的原地解法，就该登场了。

我把这三种方案的复杂度先放在一起，后面讲代码时方便对照：

方法	时间复杂度	额外空间复杂度	主要优点	主要缺点
拷贝矩阵法	O(mn) 或 O(mn*(m+n))	O(mn)	思路直接，不容易错	空间占用大
标记数组法	O(mn)	O(m+n)	时间优秀，代码简单	仍有线性额外空间
原地标记法	O(mn)	O(1)	空间最优，面试加分	逻辑细节多，容易踩坑

3. 原地解法怎么推演出来：把第 0 行和第 0 列当记录板

3.1 关键洞察：标记信息可以存回矩阵自身

现在的问题变成了：如何把标记数组里的 m + n 个布尔信息，塞进原矩阵而不用额外的数组。稍微观察一下矩阵结构就会发现，第 0 行和第 0 列本身就空闲着大量的存储位。

我们可以做一个约定：

第 0 行用来记录“某一列是否需要置 0”：如果第 j 列需要置 0，就令 matrix[0][j] = 0。
第 0 列用来记录“某一行是否需要置 0”：如果第 i 行需要置 0，就令 matrix[i][0] = 0。

这样原本的 row_flags 和 col_flags 两个数组就被“映射”到了矩阵的第 0 列和第 0 行上。相当于把要记录的数据写在一块随时可以查看的小黑板上，而这块黑板正好是矩阵自己的边缘。

这个思路和我们在工程里经常用的“哨兵节点”“占位标记”很像：与其另起炉灶维护一套状态，不如在已有数据结构里找出不会被主流程误读的位置，把标记放进去。

3.2 推演前的两个约定与难点

虽然想法很美好，但有一个绕不开的问题：第 0 行和第 0 列本身也是要被修改的。如果第 0 行里有元素本来就是 0，那第 0 行最终整行都要置 0；如果第 0 列里有元素本来就是 0，那第 0 列最终整列都要置 0。可第 0 行和第 0 列同时又承担着“记录其他行列状态”的责任。

更麻烦的是，matrix[0][0] 这个格子既是第 0 行的成员，又是第 0 列的成员。如果拿它同时记录“第 0 行是否需要置 0”和“第 0 列是否需要置 0”，一定会冲突。

所以要解决两个问题：

必须在开始动矩阵之前，先把第 0 行和第 0 列原本是否包含 0 这件事存下来。
必须给 matrix[0][0] 一个明确的定位，避免它身兼两职导致信息丢失。

我的做法是用两个布尔变量来承接第 0 行和第 0 列的原始状态：

first_row_has_zero: 第 0 行原始是否包含 0 first_col_has_zero: 第 0 列原始是否包含 0

至于 matrix[0][0] 本身，在记录内部行列状态时尽量不去依赖它。整个流程中，第 0 行负责记录列的标记，第 0 列负责记录行的标记，而 matrix[0][0] 只属于交叉点，它的最终状态由 first_row_has_zero 和 first_col_has_zero 收尾时决定。

3.3 完整的四步流程

标准原地解法按这个顺序执行：

第一步：预先扫描第 0 行和第 0 列。检查第 0 行里有没有 0，有就把 first_row_has_zero 设成 true；检查第 0 列里有没有 0，有就把 first_col_has_zero 设成 true。这一步必须在任何修改之前完成，因为第 0 行和第 0 列马上要被改造成记录板，原始信息一旦被覆盖就没地方问了。

第二步：从第 1 行第 1 列开始遍历内部区域。对于 matrix[i][j] == 0 的内部元素，把 matrix[i][0] 和 matrix[0][j] 都设成 0。这里是在向记录板“打标记”：第 i 行需要置 0，所以第 0 列的第 i 个位置记 0；第 j 列需要置 0，所以第 0 行的第 j 个位置记 0。注意遍历范围刻意从 i=1、j=1 开始，既不改动第 0 行，也不改动第 0 列，避免破坏记录板。

第三步：再次从第 1 行第 1 列开始遍历内部区域。判断条件变成：如果 matrix[i][0] == 0 或者 matrix[0][j] == 0，就把 matrix[i][j] 置为 0。这一步是真正执行“内部区域置零”的动作，判断依据全部来自第 0 行和第 0 列上的标记。

第四步：收尾处理第 0 行和第 0 列。如果 first_row_has_zero 为 true，就把整行第 0 行置为 0；如果 first_col_has_zero 为 true，就把整列第 0 列置为 0。

每一步为什么要分得这么细？核心在于：第二步只打标记不置零，第三步只置零不打标记，第四步最后修复记录板。三件事一旦混在一起，前面说过的连锁污染就会立刻出现。尤其是第四步绝不能提前做，否则第 0 行上的标记被置 0 后，第三步就完全失去了判断依据。

这里还有一个容易忽略的细节：为什么第三步还要从第 1 行第 1 列开始，而不是从第 0 行第 0 列开始？因为内部区域的置零判断依赖记录板，记录板上的第 0 行和第 0 列此时仍然是原始值加标记的状态，如果你先处理第 0 行或第 0 列，把记录板上的标记覆盖掉了，后面内部区域就不知道该听谁的。所以内部区域永远是优先处理对象，第 0 行和第 0 列永远是最后处理对象。

4. 多语言实现与逐行说明

4.1 C++ 实现

class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); if (m == 0) return; int n = matrix[0].size(); bool firstRowHasZero = false; bool firstColHasZero = false; for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { firstRowHasZero = true; break; } } for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { firstColHasZero = 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 (firstRowHasZero) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } if (firstColHasZero) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } } };

这个版本我在面试现场手写过很多次，稳定性很高。需要注意的一点是第一步扫描第 0 行和第 0 列时，一旦发现 0 就可以 break 了，因为只需要知道“有没有”，不需要知道“有几个”。

4.2 Java 实现

class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; boolean firstRowHasZero = false; boolean firstColHasZero = false; for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { firstRowHasZero = true; break; } } for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { firstColHasZero = 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 (firstRowHasZero) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } if (firstColHasZero) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } } }

Java 版本的写法跟 C++ 几乎没有差别，主要是去掉指针相关的东西。这里我习惯把 matrix.length 和 matrix[0].length 先存到局部变量里，一是可读性好，二是在循环里少几次 length 访问。

4.3 Python 实现

class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: 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

注意：在 LeetCode 等在线评测平台，List 类型已经默认导入。如果是在本地跑，要自己加from typing import List。Python 的解法和 C++/Java 本质上完全一致，只是语法更宽松。这里必须强调一下：置零操作是原地修改，函数没有返回值，所以不需要 return。

4.4 关于遍历顺序：正着扫和倒着扫都能跑，但有前提

网上能看到很多题解在第三步从左下角往右上角倒着扫，也有的是从右下角往左上角扫，看起来顺序五花八门，其实它们背后都遵循同一个原则：在读取记录板上的标记时，不能先破坏记录板。

我第三遍扫描用正序从 i=1、j=1 开始，因为无论正序还是倒序，只要不碰第 0 行和第 0 列，标记就不会丢。但有些变体写法会把“修改第 0 列”也提进第三遍循环，那种写法就必须倒着扫，否则先修改了 matrix[i][0]，后面行判断就错乱了。如果不想去记那套复杂的变体，最简单稳定的约定就是：前两遍循环一律从第 1 行第 1 列开始，第 0 行第 0 列永远留到最后处理。

5. 边界用例复盘：这些坑我已经替大家踩过了

5.1 单元素矩阵：最容易忽略的 m 或 n 为 0

matrix = [[0]]

m=1、n=1，第一步扫描第 0 行时发现 matrix[0][0]==0，于是 first_row_has_zero 为 true；扫描第 0 列时又发现 matrix[0][0]==0，于是 first_col_has_zero 也为 true。进入第二步时，i 和 j 的循环范围从 1 开始，直接跳过。第四步把第 0 行和第 0 列都置 0，结果仍然是 [[0]]，正确。

但有一种情况必须先特判：如果矩阵本身是空的，比如 m=0 或 n=0，那么 matrix[0] 的访问直接越界。所以代码开头一定要做空矩阵判断，C++ 版本里那个if (m == 0) return;不是装饰，是保命用的。Python 和 Java 版本在 LeetCode 题面上虽然保证了矩阵非空，但工程上从输入进来时并不一定可信。

5.2 只有一行或只有一列的矩阵

例如矩阵是：

[[1, 0, 1]]

只有一个 0 在第 0 行。第一步扫描第 0 行，发现 0，first_row_has_zero 为 true。第 0 列扫描会检查 matrix[0][0]=1，matrix[1][0] 不存在，所以 first_col_has_zero 为 false。第二步和第三步的循环范围都是 i=1 到逻辑上的 m-1，m=1 所以内层循环一次也不执行。第四步把整行置 0，结果是 [[0,0,0]]。

这里有个值得注意的地方：当 m=1 时，第 0 行就是全部矩阵，你对第 0 行做记录板标记其实是“拿整个矩阵当记录板”，但因为外部没有更多行需要被记录，所以第二步天然不会执行，逻辑上不会出错。同理，当 n=1 时，第 0 列就是全部矩阵，处理流程也自动退化。边界情况跑一跑，基本能验证这个算法在降维场景下是安全的。

5.3 第 0 行和第 0 列同时存在原始 0

这种情况是记录板方案最容易翻车的地方。比如：

[[0, 1], [1, 1]]

第一步会得到 first_row_has_zero=true、first_col_has_zero=true。第二步从 i=1、j=1 开始，matrix[1][1]=1，不产生任何标记。第三步也不修改内部格子。第四步把第 0 行和第 0 列全部置 0，结果是：

[[0, 0], [0, 1]]

手动验证一下，原矩阵的 0 在 (0,0)，所以第 0 行和第 0 列都要置 0，第 1 行第 1 列的 1 保留，结果完全正确。

再复杂一点：

[[0, 1, 1], [1, 1, 1], [1, 1, 0]]

这里有 0 的位置是 (0,0) 和 (2,2)。第一步记录 first_row_has_zero=true，first_col_has_zero=true。第二步扫描 i=1..2, j=1..2，发现 matrix[2][2]==0，于是标记 matrix[2][0]=0、matrix[0][2]=0。注意这一步不会去改 matrix[0][0]，所以记录板上的交叉点信息不会被损坏。第三步把 matrix[2][1] 和 matrix[1][2] 置 0，同时 matrix[2][2] 本来就是 0。第四步把第 0 行和和第 0 列全部置 0。最终结果：

[[0, 0, 0], [0, 1, 0], [0, 0, 0]]

手动检查：原始 0 在 (0,0) 和 (2,2)，所以第 0 行、第 0 列、第 2 行、第 2 列都应置 0，第 1 行第 1 列保持 1，正确。

5.4 全 0 矩阵

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

第一步就发现第 0 行和第 0 列都有 0，两个标志位都设为 true。第二步扫描内部区域，matrix[1][1]==0，所以又在记录板上写 0，不过本来就是 0。第三步把所有内部格子置 0。第四步再清一遍第 0 行和第 0 列。结果还是全 0，没问题。

但如果你小学数学不够仔细，容易把这个用例跟“空矩阵”搞混。全 0 矩阵不是没有元素，而是元素全为 0。代码处理时它是正常流程，不需要特判，但调试时建议单独跑一次，因为它的输出和输入完全一样，容易被误以为是“没生效”。

5.5 真实调试中的另一个低级错误

我早期写这类原地题目时，还犯过一个很蠢的错误：第二步扫描和第三步扫描写成了同一个双重循环，也就是一边找 0 一边改。看上去省了一次遍历，实际上第二步刚把 matrix[i][0] 标记成 0，第三步马上读到这个新标记，误以为当前行本来就要置 0，结果把整行全清了。一旦矩阵里有两个不同行不同列的 0，最终结果就会比预期多出来很多个 0。

这种问题靠眼睛看代码很难发现，最好用几个反差大的用例跑一遍。我在本地写单元测试时，最喜欢用的三个用例是：

只有左上角为 0 的矩阵，检验第 0 行和第 0 列是否被正确置零；
只有右下角为 0 的矩阵，检验内部标记是否传播到第 1 行和第 1 列之外；
全 1 矩阵，检验代码是否会把不该置零的格子误伤。

这三个用例跑完，原地解法的大部分逻辑问题都能暴露出来。

6. 这套标记思路的工程延伸：矩阵置零不止是面试题

很多朋友在刷题时会觉得这种纯粹的数字矩阵题离实际开发很远。其实“原地记录板”这个思想，在工程项目里到处都是，只是换了层皮。

举一个我工作中实际遇到的例子：处理一份二维数据透视表时，如果某一行或某一列的数据缺失率过高，通常需要在后续分析之前把整行或整列剔除。为了不污染原始统计结果，你不能在第一次扫描时边发现缺失边删除行，因为删掉行之后列的位置全变了，索引对不上。正确做法就是先扫描一遍，把哪些行、哪些列需要剔除的信息记下来，全部分析完后再统一执行删除。这跟矩阵置零的“标记后统一处理”是同一个模式。

另一个例子是游戏地图里的“视野扩散”或者“污染扩散”逻辑。某些格子触发事件后，它所在的行和列会生成特殊地形或者被标记为障碍物。如果直接在遍历过程中修改地图矩阵，后面判断到刚生成的地形又继续触发事件，就会无限扩散，地图全被污染。正确的做法一定是分两个阶段：第一遍收集触发格子的坐标，第二遍再根据坐标统一更新地图。

从算法角度讲，这套思路还可以迁移到很多相似题目上：