做算法题的朋友应该都见过“矩阵置零”这道题LeetCode 第 73 题基本是面试题库里的常客。题目本身很短给你一个 m×n 的矩阵如果某个元素是 0就把该元素所在的整行和整列全部置为 0而且要求原地修改不能另开一个同样大小的矩阵。看起来简单但真正动手写就会发现难点从来不在“怎么把 0 扩散”而在于“怎么在不借用额外空间的前提下把哪些行、哪些列需要清零这个信息保存下来”。这篇文章我会从最暴力的解法讲起一路演进到 O(1) 额外空间的标记法再给出可直接套用的 Python 和 C 实现最后把我刷题和面试时踩过的坑、总结出的经验一并整理出来。无论你是刚开始刷题的萌新还是在准备面试想优化方案的老手这篇都能给你一些实在的东西。1. 先真正理解题目再动手需求与边界很多朋友一上来就写代码结果边界条件一个接一个崩。我建议先花两分钟把题目“翻译”成人话你需要记录两类信息——哪些行含 0哪些列含 0然后把所有位于这些行或列上的元素全部改成 0。这里的关键词是“或”也就是说某个位置只要它的行号被标记或者列号被标记它就得变成 0。1.1 输入输出与边界约定题目给的矩阵维度是 m 和 n范围在 1 到 200 之间所以不用考虑空矩阵的情况。元素值可能是负数别写死判断0这种逻辑。还有一个容易被忽略的隐藏条件题目要求“原地”修改也就是你不能 new 一个矩阵再 copy 回去面试官会盯着这个点追问。举个最简单的例子输入 [ [1, 1, 1], [1, 0, 1], [1, 1, 1] ] 输出 [ [1, 0, 1], [0, 0, 0], [1, 0, 1] ]原矩阵只有 (1,1) 位置是 0所以第 1 行整行变 0第 1 列整列变 0其他位置不动。边界情况要留意三种只有一行或只有一列时逻辑必须仍然正确矩阵一开始就有多个 0 时标记不能互相干扰矩阵一个 0 都没有时结构应该原样返回。1.2 三个层级的解法演进这道题的解法基本可以分成三个档次面试时你最好能一层层给面试官演出来。第一档是暴力解复制一份完全一样的矩阵然后遍历原矩阵只要发现某个位置是 0就把副本里对应的整行整列清 0最后把副本的值导回原矩阵。这个方案空间复杂度 O(mn)思路直白但没有利用题目任何特性属于“能过但没意思”的答案。第二档是用两个布尔数组开一个长度为 m 的 row 数组记录哪些行有 0开一个长度为 n 的 col 数组记录哪些列有 0。第一遍遍历矩阵遇到 0 就更新 row[i] 和 col[j]第二遍再遍历一次只要 row[i] 或 col[j] 为真就把 matrix[i][j] 置 0。这个方案空间复杂度 O(mn)是很多人能想到的“标准解”也是面试的及格线。第三档就是这篇文章的主角不用任何数组直接借用矩阵本身的第一行和第一列当“标记板”把空间压到 O(1)。面试官听到你主动提出这个方案基本就会开始认真听你怎么讲。2. 方案选型为什么把标记写进矩阵自己很多人第一次看到 O(1) 解法时会觉得神奇其实背后的思路一句话就能说明白记录哪些行、哪些列要清零本质上是 mn 个布尔信息这些信息不一定要放在额外数组里可以直接覆盖到矩阵的第一行和第一列上。矩阵本身就是一块草稿纸用完再擦掉即可。2.1 暴力解与 O(mn) 空间解法的局限先说说前两种方案为什么不够好。暴力解的问题很直观额外复制一个矩阵空间直接翻倍面试官肯定不满意。O(mn) 的解法已经不错了但如果你仔细观察会发现它其实有点“奢侈”——row 数组和 col 数组里每个元素只存一个布尔值而这个布尔值完全可以压缩到矩阵内部的位置上。关键洞察在于当你把矩阵第一行当作 col 数组、第一列当作 row 数组后matrix[0][j] 0就表示“第 j 列需要清零”matrix[i][0] 0就表示“第 i 行需要清零”。这样就不需要额外开空间了。2.2 借矩阵自己当标记板的原理具体来说整个算法分三步走。第一步先扫描整个矩阵遇到 0 就在对应的标记位置打个记号把matrix[i][0]设为 0把matrix[0][j]设为 0。注意这里是从第 1 行第 1 列开始扫描内部区域不会碰第一行和第一列本身因为第一行第一列现在扮演的是“草稿纸”的角色不能再往上面叠加业务信息。第二步重新扫描内部区域只要发现matrix[i][0] 0或者matrix[0][j] 0就把matrix[i][j]置 0。这一步就是在“扩散”零。第三步处理第一行和第一列本身。因为标记阶段可能会覆盖第一行第一列的真实状态所以要用额外的变量提前保存它们是否原本就有 0最后再根据这些变量决定是否把第一行、第一列整段置零。这个方案空间复杂度 O(1)时间复杂度 O(mn)因为每个元素最多被访问常数次。这是理论上能压到的最优空间了因为矩阵本身就已经包含了所有输入信息你不借用任何外部存储。2.3 两个额外变量的引入逻辑这里有个非常容易踩的坑matrix[0][0]这一个位置它既是第一行的标记位也是第一列的标记位。如果第一行有 0我们会把matrix[0][0]置 0如果第一列有 0我们也会把matrix[0][0]置 0。这个位置到底代表行信息还是列信息完全说不清楚。所以必须引入两个布尔变量first_row_has_zero和first_col_has_zero在开始标记之前单独遍历第一行和第一列把它们的原始状态保存下来。有了这两个变量后面无论第一行第一列被改写成什么样最终都能还原正确结果。这也解释了为什么 O(1) 空间里仍然有两个额外变量——严格来说不是完全零额外空间但两个布尔位对于任意大小的矩阵来说都是常数级所以大家习惯直接叫它 O(1) 空间。3. 手把手实现矩阵置零完整代码与逐行拆解理论讲清楚了直接上代码。我给出 Python 和 C 两个版本逻辑完全一样风格上 Python 偏简洁C 偏工程化面试时哪个顺手用哪个。3.1 完整代码实现Python 与 Cclass 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 # 1. 备份第一行和第一列的原始状态 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 # 2. 用第一行第一列标记需要清零的行和列 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 # 3. 根据标记清理内部区域 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 # 4. 最后处理第一行和第一列 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] 0class Solution { public: void setZeroes(vectorvectorint matrix) { int m matrix.size(), n matrix[0].size(); bool firstRowHasZero false, 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; } } };3.2 逐行拆解备份、打标、清扫三阶段第一阶段是备份。为什么要单独遍历第一行和第一列因为第二阶段你在打标记时第一行第一列会被改掉。比如原矩阵第一行第三个元素原本是 1扫描内部区域时发现第 3 列有个 0于是把matrix[0][2]改成 0。这个改动本身没错因为第 3 列确实要清 0但如果你没提前备份后面就无法知道“第一行原本有没有 0”这个事实了。备份目的就是把第一行第一列从“待处理对象”中摘出去单独记录。第二阶段是打标记。双重循环严格从 (1,1) 开始跳过第一行第一列。为什么要跳过因为第一行第一列现在是“标记载体”如果遍历到matrix[0][j] 0你也去把matrix[0][0]置 0那matrix[0][0]到底是“第一列有 0”还是“第一行有 0”就分不清了整个标记系统就乱了。跳过第一行第一列之后每个内部元素产生的标记都写到第一行或第一列的对应位置语义非常清晰。第三阶段是清扫。先处理内部区域再处理第一行第一列这个顺序不能反。如果先把第一行第一列清了那内部区域做判断时matrix[0][j]已经全是 0就会把所有列都误判为需要清零结果就是整个矩阵全变成 0。只有等内部区域全部处理完毕后第一行第一列的历史使命才算完成这时候再根据备份的变量安全地处理它们。3.3 边界用例验证一步步手推光看代码可能不够直观我手推一个例子。假设输入是matrix [ [1, 1, 1], [1, 0, 1], [0, 1, 1] ]第一步备份检查第一行没有 0所以first_row_has_zero False。检查第一列matrix[0][0]1matrix[1][0]1matrix[2][0]0所以first_col_has_zero True。第二步打标记从 (1,1) 开始扫描。matrix[1][1]0于是把matrix[1][0]改成 0把matrix[0][1]改成 0。其他内部元素没有 0。此时矩阵变成[ [1, 0, 1], [0, 0, 1], [0, 1, 1] ]第三步清扫内部区域。逐个检查 (1,1)、(1,2)、(2,1)、(2,2)发现它们的行标记或列标记都为 0所以全部变成 0[ [1, 0, 1], [0, 0, 0], [0, 0, 0] ]第四步处理第一行第一列。first_col_has_zero True所以第一列全部置 0matrix[0][0]也跟着变 0。first_row_has_zero False第一行不动。最终结果[ [0, 0, 1], [0, 0, 0], [0, 0, 0] ]验证一下原矩阵中 0 在 (1,1) 和 (2,0)。所以第 1 行、第 2 行全部为 0第 1 列全部为 0。最终矩阵第 0 行中matrix[0][2]1保留因为原矩阵第 0 行既没有 0第 2 列也没有 0完全正确。这个例子把四个阶段全部覆盖了建议你在纸上自己推一遍。4. 高频问题与踩坑实录这类题真正考你什么矩阵置零这道题LeetCode 上通过率不低但面试时被问倒的人大把。我见过太多人写得出 O(mn) 解法却写不出 O(1) 解法或者写出来了但解释不清楚。这一节把我遇到的高频问题和总结的避坑技巧全列出来。4.1 为什么网上很多题解要倒序遍历如果你去看讨论区会发现不少 O(1) 解法用的是“倒序遍历”代码更短类似下面这样class Solution: def setZeroes(self, matrix: List[List[int]]) - None: m, n len(matrix), len(matrix[0]) first_col_has_zero False for i in range(m): if matrix[i][0] 0: first_col_has_zero True for j in range(1, n): if matrix[i][j] 0: matrix[i][0] 0 matrix[0][j] 0 for i in range(m - 1, -1, -1): for j in range(n - 1, 0, -1): if matrix[i][0] 0 or matrix[0][j] 0: matrix[i][j] 0 if first_col_has_zero: matrix[i][0] 0这里的核心是“倒序清理”。为什么要倒序因为第一行保存着每一列的标记如果你正序从第 0 行开始清理第一行的元素会被置 0那么所有列标记瞬间丢失后面每一列都会被误判成“需要清零”最终整个矩阵全变 0。倒序可以保证最后一轮才轮到第 0 行此时其他所有行都已经处理完毕标记的使命完成了第 0 行再怎么清都不会影响结果。两种写法的本质完全一样都是“先标记、后清扫、第一行第一列最后处理”。区别只在于你是像我上面的写法那样用两个布尔变量显式备份第一行第一列还是用倒序遍历来隐式保护第一行标记。我面试时更推荐第一种写法因为每个阶段的职责清晰面试官追问细节时你容易讲明白第二种写法的代码更短但“为什么倒序”这个问题一旦解释不清反而扣分。4.2 常见错误速查表我整理了一个错误速查表都是实际写代码时反复出现的坑错误后果正确做法未备份第一行第一列就开始打标记原始信息被覆盖最终置零错误先用两个布尔变量记录第一行第一列是否含 0清理阶段从 (0,0) 开始遍历标记位被提前清零后续判断全部失效内部区域严格从 (1,1) 开始先清理第一行第一列再处理内部区域列标记全部丢失矩阵被错误全量清零第一行第一列必须最后处理用 set 或 list 记录含 0 的行号和列号空间复杂度变成 O(mn)面试不过关把标记写进矩阵自身只留两个布尔位试图返回新矩阵不符合原地修改要求直接修改传入的 matrix函数不返回新对象判断元素是否为 0 时写成0负数元素被忽略结果错误用 0严格判断第 4 条特别常见很多朋友一上来就开row_set和col_set确实能过 OJ但空间复杂度不达标。面试官只要加问一句“能不能用 O(1) 空间”你就得现场重新想方案。与其这样不如一开始就用标记法写。第 2 条和第 3 条都是顺序问题。我的经验是只要记住“标记阶段跳过第一行第一列清理阶段最后处理第一行第一列”顺序就永远不会错。这两个阶段之间不要穿插其他操作。4.3 面试加分项与扩展思考如果你能在面试时把这题的思路延伸到其他题目面试官对你的印象会明显不一样。举几个相关的方向第一“原地”二字是这类题的灵魂。LeetCode 上还有原地旋转矩阵、原地置零、原地去除重复元素等题目本质都是“信息要在原容器中复用”。你能总结出这个共性说明你理解的是思想而不是某道题的模板。第二这道题可以变形为“只允许用位运算标记”。当 m 和 n 很大但不超过机器字长时可以用一个整数的每一位代表一列是否存在 0另一个整数代表每一行是否存在 0。这种写法空间是常量代码更酷但面试时一般不要求作为扩展了解即可。第三如果矩阵非常大大到一行都放不进内存你就需要思考分块处理按行读取用外部存储记录标记再回写。这种问题属于大数据场景面试中如果被问到可以提一下“分块 外部标记”的思路属于加分项。我个人的体会是矩阵置零是一道非常典型的思想题它不需要你背模板但需要你对数组下标有极强的掌控力。面试时讲这道题一定要按照“暴力解 → O(mn) 解 → O(1) 解”的顺序层层递进每层都要说清楚时间和空间的 trade-off。不要一上来就甩最优解因为面试官想看的不是答案本身而是你如何从约束中推导出答案。把第一行第一列比喻成“草稿纸”把两个布尔变量比喻成“备份草稿纸原始状态的小纸条”很多面试官都会点头表示理解。最后分享一个我刷题时养成的小习惯任何 O(1) 空间的原地算法题我都会先写一个 O(mn) 或 O(mn) 空间的暴力版再用它作为对照验证优化版的正确性。矩阵置零这种题尤其适合这种打法因为你可以随机生成十几个矩阵对比暴力版和优化版输出是否完全一致。这个习惯帮我抓出了不少边界 bug比如差点漏掉“第一列本身有 0”的情况。你也试试比只看题解有用得多。