矩阵置零这道题我在面试别人和自己刷题的时候都见过太多次了。题目描述看第一眼都觉得简单得像送分题一个 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*(mn))因为每遇到一个 0 就要立刻横向纵向扫一遍。复制矩阵本身要 O(mn) 的额外空间。如果矩阵规模一旦上去比如 1000×1000光是复制一份就要占据和原矩阵同样的内存这在很多竞赛或工程场景下是不可接受的。即使把拷贝矩阵法优化成“先记录所有 0 坐标再统一置零”也就是先扫描一遍拿到所有 (i,j) 零坐标再针对每个坐标置零对应行列避免了 mn 的二次循环但 O(mn) 的额外空间这个硬伤仍然存在。作为保底答案可以但不该止步于此。2.2 更好想的标记数组法O(mn) 空间顺着“先记录位置再统一处理”的思路往下走大多数刷题的人会写出第二个版本用两个一维布尔数组一个标记哪些行需要置 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(mn)。注意这里不再需要二维辅助数组因为“需要置零的行集合”和“需要置零的列集合”各自只需要一维的信息。这也是大部分面试官能够接受的次优解。但从优化角度看mn 的额外空间还不够极致。如果 m 和 n 都是 10^4 的规模两个布尔数组加起来就是 20000 个 bool虽然不算大但题目进阶要求往往写的是“尽量使用 O(1) 的额外空间”。于是第三个版本也就是常说的原地解法就该登场了。我把这三种方案的复杂度先放在一起后面讲代码时方便对照方法时间复杂度额外空间复杂度主要优点主要缺点拷贝矩阵法O(mn) 或 O(mn*(mn))O(mn)思路直接不容易错空间占用大标记数组法O(mn)O(mn)时间优秀代码简单仍有线性额外空间原地标记法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。注意遍历范围刻意从 i1、j1 开始既不改动第 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(vectorvectorint 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 关于遍历顺序正着扫和倒着扫都能跑但有前提网上能看到很多题解在第三步从左下角往右上角倒着扫也有的是从右下角往左上角扫看起来顺序五花八门其实它们背后都遵循同一个原则在读取记录板上的标记时不能先破坏记录板。我第三遍扫描用正序从 i1、j1 开始因为无论正序还是倒序只要不碰第 0 行和第 0 列标记就不会丢。但有些变体写法会把“修改第 0 列”也提进第三遍循环那种写法就必须倒着扫否则先修改了 matrix[i][0]后面行判断就错乱了。如果不想去记那套复杂的变体最简单稳定的约定就是前两遍循环一律从第 1 行第 1 列开始第 0 行第 0 列永远留到最后处理。5. 边界用例复盘这些坑我已经替大家踩过了5.1 单元素矩阵最容易忽略的 m 或 n 为 0matrix [[0]]m1、n1第一步扫描第 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]]正确。但有一种情况必须先特判如果矩阵本身是空的比如 m0 或 n0那么 matrix[0] 的访问直接越界。所以代码开头一定要做空矩阵判断C 版本里那个if (m 0) return;不是装饰是保命用的。Python 和 Java 版本在 LeetCode 题面上虽然保证了矩阵非空但工程上从输入进来时并不一定可信。5.2 只有一行或只有一列的矩阵例如矩阵是[[1, 0, 1]]只有一个 0 在第 0 行。第一步扫描第 0 行发现 0first_row_has_zero 为 true。第 0 列扫描会检查 matrix[0][0]1matrix[1][0] 不存在所以 first_col_has_zero 为 false。第二步和第三步的循环范围都是 i1 到逻辑上的 m-1m1 所以内层循环一次也不执行。第四步把整行置 0结果是 [[0,0,0]]。这里有个值得注意的地方当 m1 时第 0 行就是全部矩阵你对第 0 行做记录板标记其实是“拿整个矩阵当记录板”但因为外部没有更多行需要被记录所以第二步天然不会执行逻辑上不会出错。同理当 n1 时第 0 列就是全部矩阵处理流程也自动退化。边界情况跑一跑基本能验证这个算法在降维场景下是安全的。5.3 第 0 行和第 0 列同时存在原始 0这种情况是记录板方案最容易翻车的地方。比如[[0, 1], [1, 1]]第一步会得到 first_row_has_zerotrue、first_col_has_zerotrue。第二步从 i1、j1 开始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_zerotruefirst_col_has_zerotrue。第二步扫描 i1..2, j1..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. 这套标记思路的工程延伸矩阵置零不止是面试题很多朋友在刷题时会觉得这种纯粹的数字矩阵题离实际开发很远。其实“原地记录板”这个思想在工程项目里到处都是只是换了层皮。举一个我工作中实际遇到的例子处理一份二维数据透视表时如果某一行或某一列的数据缺失率过高通常需要在后续分析之前把整行或整列剔除。为了不污染原始统计结果你不能在第一次扫描时边发现缺失边删除行因为删掉行之后列的位置全变了索引对不上。正确做法就是先扫描一遍把哪些行、哪些列需要剔除的信息记下来全部分析完后再统一执行删除。这跟矩阵置零的“标记后统一处理”是同一个模式。另一个例子是游戏地图里的“视野扩散”或者“污染扩散”逻辑。某些格子触发事件后它所在的行和列会生成特殊地形或者被标记为障碍物。如果直接在遍历过程中修改地图矩阵后面判断到刚生成的地形又继续触发事件就会无限扩散地图全被污染。正确的做法一定是分两个阶段第一遍收集触发格子的坐标第二遍再根据坐标统一更新地图。从算法角度讲这套思路还可以迁移到很多相似题目上如果题目改成“把包含 0 的行和列移动到矩阵末尾”标记思路依然成立如果是稀疏矩阵可以用两个集合存行号和列号那就是 O(mn) 标记数组法的哈希表变体如果要求返回一个新矩阵而不改动原矩阵那本质就是拷贝矩阵法的应用场景没必要强行原地。我个人的体会是矩阵置零更像是一道“空间换时间”和“时间换空间”的训练题。它不考复杂的数据结构也不考高深的数学推导单看你能否在普通数组操作里守住信息的边界。掌握了这道题的思考方式以后碰到任何“原地修改”型题目比如原地旋转、原地删除、原地哈希都会少走很多弯路。最后再分享一个实用小技巧如果你在面试中写了原地解法一定要在代码注释里把第 0 行和第 0 列是“记录板”这件事写清楚。因为这段代码如果不配注释三个月后的你再看也得花好几分钟想明白为什么有两个布尔变量但有了注释别人一眼就能看出你的设计意图这在面试评分上是个不小的隐性加分项。