企业官网建设流程全解析

矩阵置零这道题我太熟了，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(m+n) 再到 O(1)

顺着“先标记后结算”的思路，解法可以分三个层次。

暴力复制法：复制一份一模一样的矩阵，在副本上遍历原始矩阵，发现原始矩阵哪个位置是 0，就在副本上把对应行和列全部置零。最后把副本赋值给原矩阵。这个方案思路最直白，但是额外空间是 O(mn)，完全不符合进阶要求。

行标记数组法：准备两个数组 row[m] 和 col[n]，初始都是 false。第一次遍历矩阵，遇到 0 就把 row[i] 和 col[j] 标记为 true。第二次遍历矩阵，只要 row[i] 或者 col[j] 是 true，就把这个格子置零。这样时间 O(mn)，空间 O(m+n)，比暴力复制省了很多，也是面试时比较容易想到的“简单改进方案”。

原地标记法：不额外开 row 和 col 数组，而是直接借用矩阵的第一行和第一列当标记区。空间降到 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 记录第一行原本是否存在 0，colFlag 记录第一列原本是否存在 0。这两个变量是 O(1) 的额外空间，不违反题目要求。

有了这两个快照，处理顺序才能安全确定下来：

1. 扫描账本区（第一行和第一列）的原始状态，存入 rowFlag 和 colFlag。
2. 遍历子矩阵（i >= 1, j >= 1），遇到 0 就更新账本区。
3. 再次遍历子矩阵，根据账本区信息把内部格子置零。
4. 最后处理第一行和第一列。先根据 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(vector<vector<int>>& 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(m+n) 的行列数组法，再“偶然想到”可以把这个数组塞进矩阵自身，展示出优化的过程感。直接甩最优解，容易给人一种背题的印象。

这套“标记账本”的思路，往后做任何二维矩阵的原地改写题都用得上，值得你花点时间吃透。