矩阵置零这道题我太熟了LeetCode 第 73 题也是我面试时特别喜欢拿出来考候选人的一道。题面简单到不能再简单给你一个 m×n 的矩阵矩阵里只要有格子是 0就把这一整行和这一整列全部变成 0。限制条件就一个原地操作额外空间只能 O(1)。第一次做这题的人十个有九个都栽在“边遍历边置零”这个坑里跑出一个全 0 矩阵之后才意识到事情没那么简单。这篇文章我把这道题从暴力解法到最优原地解法的思路完整拆开手把手推一遍执行过程再把我踩过的一些坑和面试追问整理出来。适合正在刷题准备面试的同学也适合想弄明白“原地算法到底在优化什么”的开发者。1. 题目理解与思路演进1.1 题面拆解与隐藏条件先把题目的三个信息点拆清楚。输入是 m×n 矩阵操作规则是只要 matrix[i][j] 0第 i 行和第 j 列的所有元素都要变为 0。注意是“所有元素”包括那些原本不是 0 的格子。输出直接修改原矩阵不能返回一个新矩阵。看到“原地”这个词很多人第一反应是那无所谓我遍历一遍遇到 0 就把整行整列改了。这就是最大的坑。为什么因为你在遍历的过程中修改了矩阵后续遍历读到的格子就不是原始状态了。矩阵里只要有一个 0经过你“边扫边改”很快所有非 0 格子都会被误判成 0最终整个矩阵变成全 0。举个最简单的例子1 0 1 1 1 1 1 1 1如果你从 (0,0) 开始按行遍历看到 (0,1) 是 0立刻把第 0 行和第 1 列全部置零。此时第 0 行已经全是 0 了。接着你遍历到 (0,2)发现它是 0其实是你刚改的于是又把第 2 列全部置零。连锁反应下去整个矩阵全 0。而这个矩阵原本只需要把第 0 行和第 1 列置零第 (2,2) 这个位置明明应该保持 1。所以这道题的核心矛盾是你必须先知道哪些行、哪些列需要清零之后统一执行清零操作。也就是“先标记后结算”。1.2 从 O(mn) 到 O(mn) 再到 O(1)顺着“先标记后结算”的思路解法可以分三个层次。暴力复制法复制一份一模一样的矩阵在副本上遍历原始矩阵发现原始矩阵哪个位置是 0就在副本上把对应行和列全部置零。最后把副本赋值给原矩阵。这个方案思路最直白但是额外空间是 O(mn)完全不符合进阶要求。行标记数组法准备两个数组 row[m] 和 col[n]初始都是 false。第一次遍历矩阵遇到 0 就把 row[i] 和 col[j] 标记为 true。第二次遍历矩阵只要 row[i] 或者 col[j] 是 true就把这个格子置零。这样时间 O(mn)空间 O(mn)比暴力复制省了很多也是面试时比较容易想到的“简单改进方案”。原地标记法不额外开 row 和 col 数组而是直接借用矩阵的第一行和第一列当标记区。空间降到 O(1)。这也是题目进阶要求的解法。三种方案的对比我放在下面方案时间复杂度额外空间是否原地是否容易出错暴力复制O(mn)O(mn)否低行列标记数组O(mn)O(mn)否低原地标记O(mn)O(1)是中“空间 O(1)”听着很玄实际就是把原来那两个数组存到哪里的问题。既然不能用额外数组那就在矩阵自己身上找地方存第一行和第一列本身就是两个天然的“数组”。2. 原地标记法的核心思想2.1 把第一行和第一列当成账本我习惯把第一行、第一列称为“账本区”。思路是这样遍历所有不在第一行、不在第一列上的格子也就是 i 1 且 j 1 的那块子矩阵。如果发现 matrix[i][j] 0我们不在原位置动手而是跑到账本区去记一笔账把 matrix[i][0] 置为 0再把 matrix[0][j] 置为 0。这相当于在说第 i 行需要清空第 j 列需要清空。因为这个账本上的信息最终会被用于执行清空操作所以这个方案又叫“用标记区的格子存储行列的零状态”。有人会问为什么偏偏选第一行第一列而不是最后一行最后一列本质上选哪一行哪一列都行只要这一行和这一列不参与主要遍历即可。选第一行第一列是因为遍历从小到大最自然而且题目给的矩阵一定有第一行第一列逻辑上最好解释。等所有内部格子的账都记完之后再进行第二轮遍历只要看到 matrix[i][0] 0 或者 matrix[0][j] 0就把 matrix[i][j] 置为 0。因为账本已经把“哪些行哪些列需要清”记录好了此时读账本执行清空结果是准确无误的。整个过程一句话总结先记账后清账。这也是这道题区别于普通矩阵遍历题的核心思想。2.2 账本区自身的特殊身份这里有个很容易忽略的细节第一行和第一列既是账本区也是需要被清理的对象。如果第一行上原本就有 0那么第一行这一整行都要被清空。但问题来了第一行在记账时被用来存储“哪些列需要清空”的信息matrix[0][j]。如果我们把第一行当成普通行一样处理在清理阶段直接用 matrix[0][j] 读取信息来决定清空哪些列第一行本身的“是否需要清空”状态就会被覆盖。更麻烦的是matrix[0][0] 这个格子特别特殊。它同时位于第一行和第一列的交叉点如果 matrix[0][0] 是 0那它既表示“第一行要清”也表示“第一列要清”。但我们只看这个值根本区分不了到底是行要清、列要清还是两者都要清。解决办法是在开始记账之前先用两个 bool 变量把第一行、第一列的原始状态“拍快照”保存下来。rowFlag 记录第一行原本是否存在 0colFlag 记录第一列原本是否存在 0。这两个变量是 O(1) 的额外空间不违反题目要求。有了这两个快照处理顺序才能安全确定下来扫描账本区第一行和第一列的原始状态存入 rowFlag 和 colFlag。遍历子矩阵i 1, j 1遇到 0 就更新账本区。再次遍历子矩阵根据账本区信息把内部格子置零。最后处理第一行和第一列。先根据 rowFlag 清第一行再根据 colFlag 清第一列。最后一步必须在最后做的原因很清楚如果先清第一行matrix[0][j] 这一排账本会被全部覆盖成 0第二步结算子矩阵的时候就拿不到正确信息了。2.3 信息流是单向的顺序不能乱整个算法的数据流是这样的子矩阵中出现 0 - 账本区登记matrix[i][0] 0, matrix[0][j] 0 ↓ 子矩阵再次遍历 - 读账本区执行清空matrix[i][j] 0 ↓ 处理第一行 - 用 rowFlag 清第一行全部格子 ↓ 处理第一列 - 用 colFlag 清第一列全部格子关键点在于账本区的信息一旦被写入就不能在结算前被修改。而第一行第一列自身又是最后才被清空的所以结算子矩阵时账本还完好无损。这两个“最后”保证了整个过程中信息不会丢失。理解了这个单向信息流代码写起来就非常顺手了。3. 代码实现与手推全过程3.1 C 版参考实现与逐段解析我平时用 C 刷题完整代码如下class Solution { public: void setZeroes(vectorvectorint matrix) { int m matrix.size(); int n matrix[0].size(); bool firstRowHasZero false; bool firstColHasZero false; // 步骤1先检查第一行和第一列本身有没有0 for (int j 0; j n; j) { if (matrix[0][j] 0) { firstRowHasZero true; } } for (int i 0; i m; i) { if (matrix[i][0] 0) { firstColHasZero true; } } // 步骤2遍历子矩阵用第一行第一列做标记 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; } } } // 步骤3根据标记把子矩阵中的格子置零 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; } } } // 步骤4最后处理第一行和第一列 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; } } } };这个写法最大的优点是逻辑非常对称先检查特殊行和特殊列再处理中间块最后收尾处理特殊行和特殊列。每个循环的职责都很单一不容易写乱。顺带提一下我在步骤3判断的时候用的是matrix[i][0] 0 || matrix[0][j] 0。这里的||代表“只要所在的行需要清或者所在的列需要清我就得被清”。注意不要写成那是“行和列同时需要清才清”结果会漏掉很多格子。3.2 用示例矩阵亲手推一遍我拿 LeetCode 官方的示例2来演示因为这个例子包含了第一行和第一列同时有 0 的复杂情况。初始矩阵 0 1 2 0 3 4 5 2 1 3 1 5第一步检查第一行和第一列第一行[0, 1, 2, 0]包含 0所以 firstRowHasZero true。第一列[0, 3, 1]包含 0所以 firstColHasZero true。第二步遍历子矩阵也就是第 1 行到第 2 行、第 1 列到第 3 列matrix[1][1] 4不是 0不动。matrix[1][2] 5不是 0不动。matrix[1][3] 2不是 0不动。matrix[2][1] 3不是 0不动。matrix[2][2] 1不是 0不动。matrix[2][3] 5不是 0不动。这个例子里子矩阵没有 0所以账本区没被写入新标记。但注意第一行中的 matrix[0][0] 0 和 matrix[0][3] 0 本来就是 0因此它们仍然能起到标记作用。第三步结算子矩阵。以 (1,3) 为例检查矩阵matrix[1][0] 3不为 0再检查matrix[0][3] 0为 0所以把 matrix[1][3] 置零。同理(2,3) 也会被置零。第四步处理第一行和第一列。因为 firstRowHasZero 是 true把第一行全部置零因为 firstColHasZero 是 true把第一列全部置零。最终结果0 0 0 0 0 4 5 0 0 3 1 0和官方输出完全一致。3.3 Python 版与跨语言实现的差异Python 的实现逻辑一模一样只是语法上更省事def set_zeroes(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)) 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: matrix[0] [0] * n if first_col_has_zero: for i in range(m): matrix[i][0] 0用any检查第一行、第一列有没有 0代码会简洁不少。需要注意 Python 里matrix[0] [0] * n是整行替换这在原地操作的前提下可以接受因为我们只是改了引用并没有额外开辟第二个矩阵。如果特别较真也可以写成逐个元素赋值。不同语言的踩坑点不太一样。C 要小心matrix[0]的引用Java 要小心二维数组可能是不规则数组Python 要小心[[0] * n] * m这种初始化方式会生成 m 个指向同一行的引用。不过只要牢记算法顺序语言层面的差异都不是大问题。4. 边界情况与高频易错点4.1 只有一行或一列的矩阵当矩阵是 1×n 时代码走 m 1 的分支。循环for (int i 1; i m; i)直接跳过子矩阵不存在回退到第一步用 firstRowHasZero 处理第一行。如果这一行里本来就有 0最终整行变 0如果没有 0矩阵不变。当矩阵是 m×1 时同理for (int j 1; j n; j)跳过最后靠 firstColHasZero 处理第一列。最极端的情况是矩阵只有一个格子比如[[0]]。此时 firstRowHasZero 和 firstColHasZero 都为 true最后先清第一行再清第一列格子还是 0结果正确。如果初始是[[5]]两个 flag 都是 false矩阵保持不变也正确。还有一种是空矩阵即 m 0 或者 n 0。LeetCode 的约束里矩阵至少是 1×1但作为函数稳妥起见可以先判断if (matrix.empty() || matrix[0].empty()) return;。这个防御性写法在实际工程里很有必要。4.2 最容易踩的坑把账本区读成“结算后的结果”我在带人做这道题时发现很多人第一次写对后第二次隔几天再写又会出错出错的点集中在结算顺序。典型错误写法是这样的先扫描一遍记录标记然后立即把第一行按标记清空接着再处理子矩阵。看起来没毛病但问题在于清空第一行会把 matrix[0][j] 这些账本全变成 0子矩阵结算时无论哪一列都会命中“第一行有标记”结果整个矩阵全变 0。用前面示例2演示这个错误原始 matrix[0][3] 0它标记第 3 列需要清空。如果先清第一行matrix[0][3] 仍然是 0看不出来区别。如果原始 matrix[0][3] 5而第一行某个其他位置有 0导致第一行需要清空时matrix[0][3] 就会被覆盖成 0。这时子矩阵结算看到 matrix[0][3] 0就会认为“第 3 列需要清空”把原本不该清空的一整列都清了。所以正确的顺序一定是先处理子矩阵最后处理第一行和第一列。这样账本在需要读取时永远保持“记账完成但未结算”的状态。4.3 为什么不能只用一个 flag 标记第一行有些题解版本只用一个 flag 标记第一列把 matrix[0][0] 当作第一行的标记。这个写法也能通过但需要从最后一行倒着遍历避免覆盖。我个人不推荐初学者一开始就写这个版本。只用 matrix[0][0] 的语义是matrix[0][0] 0 表示第一行需要清空firstColZero 变量表示第一列需要清空。如果原始矩阵的 matrix[0][0] 恰好是 0而第一列其他位置没有 0那 matrix[0][0] 同时承担了两个含义等价于第一列也需要清因为第一列一定会被清空这本质上没有歧义。但它容易让读代码的人困惑“到底 matrix[0][0] 是原始 0还是被标记成 0 的”我坚持用两个 bool 变量的版本不是因为性能而是因为语义清晰。面试时你能把每个变量的含义解释清楚比写一个更“巧妙”但难读的版本得分更高。4.4 设计测试用例时要注意什么我平时会拿这几类用例自测矩阵不含 0结果应该和原始矩阵完全相同。0 在中间部位只有该行和该列被清。0 在第一行和第一列测试两个 flag 是否正确。多个 0 分布在不同的行和列测试标记信息是否会互相覆盖。单行、单列、单个元素三种极端尺寸。这几个用例覆盖了这道题 90% 的边界情况。不想自己构造的话直接拿 LeetCode 官方两个示例跑一遍再加上一个单行用例[[1, 0, 2]]和一个单列用例[[1], [0], [2]]基本就稳了。5. 复杂度分析与面试进阶5.1 为什么 O(mn) 时间就是最优先看时间复杂度。整个过程遍历了矩阵三次第一次检查首行首列第二次记账第三次结算。加上首行首列的最后清理总遍历次数是常数级的 4 次。每次遍历都是 O(mn) 的量级因为所有格子都要被访问所以总时间复杂度 O(mn)。能不能再快不行。最朴素的理由矩阵每个格子至少要读一次才能知道它是不是 0而一旦存在 0受影响的整行整列都要被写为 0这些写入操作在最坏情况下也要覆盖 O(mn) 个格子。所以读和写的下界都被 O(mn) 锁死了。任何声称“快于 O(mn) 完成本题”的解法都是不对的。再看空间。我们只用了两个 bool 变量空间复杂度 O(1)。如果把两个 bool 标记也省了理论上做不到因为第一行和第一列的原始状态信息必须存在某个地方。也许可以压缩到只用一个变量但信息的存储需求并没有消失只是换了一个形式。5.2 面试官会追问的延伸问题这道题在面试里经常作为“热身题”出现随后面试官会顺手抛几个衍生问题。第一个追问如果矩阵特别大内存中放不下怎么办这种场景下“读取”的成本变高常见思路是分块处理每次只加载矩阵的一部分到内存维护行和列的标记信息用到行扫描。更实际的做法是既然标记信息本质上只需要 m n 个布尔值可以直接把标记落在磁盘或者外部存储上分块读入后按标记结算。本质思想和本题完全一致只是把“账本区”从矩阵首行首列换到了外部存储。第二个追问如果矩阵是稀疏矩阵即 0 很少怎么优化可以只记录 0 的坐标然后对行、列坐标去重最后执行置零。这在 0 非常少的场景下能省去多次矩阵遍历空间开销 O(k)k 是 0 的个数。不过在 LeetCode 的约束下这个思路并不会比 O(1) 空间的原地方案更好所以通常只作为开放讨论题。第三个追问能不能做到稳定的一次遍历有种写法是在遍历过程中同时维护“当前行是否要清空”的变量把行状态实时结算列状态留到回头处理。这种写法省掉了第三次遍历但代码复杂度明显上升而且要非常小心当前行结算后对后续列状态的影响。我通常是先指出“三次遍历的 O(mn) 已经是渐进最优”再补充说“能合并成两遍甚至接近一遍但可读性会下降工程上不推荐”面试官一般会满意。5.3 这道题和相关题型的共同套路矩阵置零属于非常典型的一类题原地状态转换。同类的还有 LeetCode 289 生命游戏、48 旋转图像、130 被围绕的区域。它们的共同点是直接修改原数组时旧状态和新状态会互相干扰所以需要引入“状态编码”或“标记区”来过渡。我把这种题目的通用解法总结成一句话当你暂时不能直接改写数据时先把所有需要基于旧状态做的判断做完把结论编码到某个可访问的存储区最后统一更新。这个思路在工程里也很有用比如数据库里的“先写日志再落库”、异步任务里的“先标记后处理”本质都是先记账后结算。刷题刷到这里真正有价值的不只是这道题的代码而是你开始形成一种条件反射看到“原地修改 需要基于原始状态判断”的组合第一反应就是找标记空间。第一行、第一列是题面给你的免费空间千万别浪费。我个人做这道题时还有一些小习惯写代码之前一定先手动跑一遍示例把每个循环要操作的范围用笔圈出来。尤其是 i 和 j 的边界是从 1 开始还是从 0 开始经常决定了你要不要额外处理第一行。把这个问题想清楚再动键盘基本一遍就能写出正确答案。另一个体会是面试时不妨先讲 O(mn) 的行列数组法再“偶然想到”可以把这个数组塞进矩阵自身展示出优化的过程感。直接甩最优解容易给人一种背题的印象。这套“标记账本”的思路往后做任何二维矩阵的原地改写题都用得上值得你花点时间吃透。