矩阵置零最优解：O(1)空间原地标记法详解

近几年面试算法题里面矩阵类问题一直是高频考点而矩阵置零LeetCode 73几乎是所有刷题指南里的常客。这题表面上看很简单——遍历矩阵遇到 0 就把整行整列清零但真正动手做的时候大多数人第一次都会卡在空间复杂度上题目要求你用原地算法也就是常数级额外空间这意味着你不能随手开两个数组来记哪行哪列要清空。我最早刷这题的时候也踩过坑差点直接用一个visited矩阵复制一份答案交上去。后来认真把三种解法都吃透才发现这题其实是考察“能不能把标记信息藏进原数据里”的思路题。网上关于这题的题解很多但大多只贴代码不讲为什么尤其是不讲“为什么首行首列做标记时必须倒着遍历”这个关键点。这篇就把我的思考过程、完整推导、代码实现和实际踩坑记录都写出来希望能帮你一次性把这类“原地标记”的套路吃透。这篇内容适合正在刷 LeetCode 热门 100 题的选手、准备面试需要快速复习算法题的人以及想搞懂“O(1) 额外空间到底怎么省”的读者。我会从最直观的暴力解法讲起一步步压缩空间复杂度最后给出能直接在面试里写出来的干净版本顺带补充几个面试官爱问的变形题。1. 题目到底在考什么核心难点不是“清行清列”而是“信息存储”1.1 题目描述与本质题目本身不长给定一个m x n的矩阵如果某个元素为 0则将其所在行和列的所有元素都设为 0。要求原地操作。“原地操作”这四个字才是关键。很多人在第一次读完题后会想这有什么难的我用一个同样大小的矩阵复制原数据然后根据新矩阵里的 0 去原矩阵里清行清列不就行了确实可以但那样需要 O(m×n) 的额外空间完全不符合题目的进阶要求。这题真正考察的本质问题其实是当你遍历矩阵发现一个 0 的时候这个“0 的信息”如何被可靠地保存下来。因为你一旦把某行清成 0这个 0 会和原本的 0 混在一起后面再遍历时就分不清哪些是原始 0、哪些是后来被清出来的 0。所以问题的核心矛盾是信息必须保存下来否则清着清着自己就乱了空间必须压缩到 O(1)不能靠辅助数组这就像你在黑板上做题突然发现草稿纸不够用了只能把演算过程写在黑板的角落里但你又不能影响本来要展示的答案。所有这类“原地算法”的题目本质上都是这个矛盾如何在有限的空间里借位置来存信息。1.2 为什么这题是面试高频在 LeetCode 热门 100 题和各大公司的题库里矩阵置零的出镜率一直很高原因有三个。第一它考察的是数组下标运算和边界条件。矩阵问题本身就容易在row、col的边界上出错这题更是如此——标记阶段和清空阶段的边界逻辑稍有疏忽就会把不需要清空的行列也顺手清掉。第二它考察空间复杂度的敏感度。很多候选人能写出 O(mn) 的解但要求优化到 O(1) 时就会卡住。面试官特别喜欢用这题来试探你对“空间换时间、时间换空间”的理解程度。第三它有一个非常经典的“信息标记”套路——利用矩阵自身的首行首列作为标记区——这个套路在后续很多题目里都能复用比如岛屿类问题、生命游戏等。面试官看你写这题其实也在看你有没有举一反三的潜力。1.3 三种空间复杂度的解法全貌在展开详解之前我先把这道题常见的几条路捋一下便于你心里有个全局图解法额外空间思路适用场景暴力复制O(m×n)复制矩阵按副本的 0 去清原矩阵最容易理解但空间最差面试只能用来开场行列表格O(mn)用两个布尔数组记录哪些行/列含 0空间可以接受代码简单很多教材默认解法原地标记O(1)用矩阵首行首列当标记位最优解也是这题真正的考点原地标记单独变量O(1)用单独变量额外处理首行/首列本身含 0 的情况最优解的最稳写法推荐掌握其中第 4 种是我今天重点要讲的。它比第 3 种更严谨因为第 3 种在「首行或首列本身包含 0」时会翻车而第 4 种用两个变量把这种情况单独拎出来处理逻辑更清晰。2. 从暴力到 O(mn) 空间先易后难的思考路径2.1 暴力复制法为什么它不是好的面试答案先来说说最简单的方法——复制矩阵。这个方法的思路极其直白先new一个同样大小的矩阵把原矩阵的值全部拷过去然后遍历这个副本每遇到一个 0就在原矩阵上把对应行和列全部置 0。代码写出来大概长这样伪代码层面def setZeroes_brute(matrix): m, n len(matrix), len(matrix[0]) copy [row[:] for row in matrix] for i in range(m): for j in range(n): if copy[i][j] 0: for r in range(m): matrix[r][j] 0 for c in range(n): matrix[i][c] 0这个解法正确性没问题但有两个致命问题。第一个是空间复杂度 O(m×n)在面试中直接说这个答案等于告诉面试官你还没理解“原地”这两个字的重量。第二个更隐蔽——这个方法是把“哪些行哪些列要清空”这个信息存储在副本矩阵里的一旦副本和原矩阵不同步就会出错。虽然副本不会边遍历边修改因为遍历的是副本所以正确性保住了但它完全没体现任何算法思维属于“暴力枚举”里的最暴力。我可以明确说面试时如果你只给出这版大概率会被要求继续优化。所以这步只用来确认你读懂了题绝不能停在这里。2.2 行列布尔标记法空间从 O(m×n) 降到 O(mn)聪明的读者到这里自然会想到我真正需要记住的不是每个位置原来是几而是哪几行、哪几列需要置零。这两份信息各自只需要一个长度 m 的数组和一个长度 n 的数组也就是 O(mn) 的空间。这就是 O(mn) 解法——用两个布尔数组row_zero[i]表示第 i 行是否包含 0col_zero[j]表示第 j 列是否包含 0遍历一遍矩阵遇到matrix[i][j] 0就同时把row_zero[i]和col_zero[j]置为 True。第二遍遍历时只要row_zero[i]或col_zero[j]为 True就把matrix[i][j]置为 0。这个解法最大的优点是逻辑清晰、不容易写错。它把“收集信息”和“执行清空”两个阶段完全分开了第一遍只负责记录第二遍只负责执行。边界条件也少不容易踩坑。2.3 布尔标记法的代码实现与边界注意事项下面给一个完整可跑的 Python 实现def setZeroes(matrix): m, n len(matrix), len(matrix[0]) row_zero [False] * m col_zero [False] * n # 第一遍收集信息 for i in range(m): for j in range(n): if matrix[i][j] 0: row_zero[i] True col_zero[j] True # 第二遍执行清空 for i in range(m): for j in range(n): if row_zero[i] or col_zero[j]: matrix[i][j] 0这个代码有两个细节值得注意。一个是row_zero和col_zero的初始化必须用[False] * m这种形式不能用[[False] * n] * m那种嵌套乘法初始化二维数组——后者会把同一块内存地址复制多份改一个就全跟着变。另外就是第二遍遍历时判断条件应该用 or 而不是 and意思是“只要行或列有 0当前位置就要清零”。虽然这个解法已经比暴力法好太多了但面试官大概率还会追问一句“能不能把额外空间降到 O(1)”这时候就是这题真正的高潮了。3. O(1) 空间的核心思路把首行首列当成你的“黑板书”3.1 核心思路把标记信息存进矩阵自身回到最初的那个矛盾我们需要记录 mn 个布尔信息但额外空间只能用 O(1)。怎么办答案就藏在这个矛盾里——既然不能开新的数组来存标记那能不能用矩阵自己的某一行、某一列来当标记位当然能。矩阵的首行第 0 行和首列第 0 列就是现成的两个“天然数组”首行有 n 个格子正好可以标记 n 列的信息首列有 m 个格子正好可以标记 m 行的信息。它们自身的存储空间不需要额外申请就藏在原来的矩阵里。具体做法是这样的第一遍遍历矩阵除首行、首列之外的所有区域遇到matrix[i][j] 0时把matrix[i][0]和matrix[0][j]标记为 0。这里的matrix[i][0]首列就相当于原来row_zero[i]的角色matrix[0][j]首行就相当于原来col_zero[j]的角色。第二遍再遍历除首行、首列之外的区域按matrix[i][0] 0或matrix[0][j] 0来决定是否把matrix[i][j]清成 0。最后再根据事先保存的状态决定首行和首列本身是否要全清成 0。用我自己的话来说这就像你在整理书包时发现没有多余的纸了于是直接在书的扉页上做笔记。书扉页本来就存在的你没有额外增加任何东西但它帮你留住了一堆重要的信息。3.2 为什么要用首行首列而不是别的行有读者可能会疑惑为什么偏偏是首行和首列用最后一行、最后一列行不行答案是行但没必要。关键在于首行和首列有一个天然优势——它们是全矩阵的“边界”。当你在遍历内部区域时首行和首列上的单元格只会被当作标记位使用不会被内部区域的清空逻辑重复影响。如果你用中间某一行当标记行那这一行本身就可能是需要清空的行标记和清空就会互相干扰逻辑瞬间复杂好几个量级。当然你也可以选择把最后一行、最后一列当标记区只要你能在代码里把“标记区”和“数据区”的边界卡对。但面试里最优解就是首行首列这是最经典的写法也不会因为某个角落的 0 导致标记区自相矛盾记忆和复现成本都最低。3.3 容易翻车的地方首行首列自己本身就是 0 怎么办这是整个题最阴险的陷阱。假如矩阵的matrix[0][0]本身就是 0那么首行和首列都要全部清成 0。但我们刚才是用matrix[0][0]这个格子同时当首行的标记值和首列的标记值的——它一个格子同时兼任两个角色如果它本身就是 0那说明首行、首列都需要清空这一点其实还好。真正的麻烦在于首行、首列里其他位置的原始 0 也会被“清空阶段”误当作标记值来读。举个例子假设matrix[0][3]原本是 0而它正好又会被我们拿来标记“第 3 列有 0”。这时候问题来了第一遍遍历时我们会把matrix[0][3]这个位置标记成 0因为它是第 0 行的一个 0也是首行的一个单元格。单看matrix[0][3]我们根本分不清它到底表示“第 3 列有 0”还是“首行原本就有 0”。为了彻底避开这个混沌状态最优解的写法里要引入一个“辅助变量”或者用非常小心但难读的位运算。这也是我在第 1.3 节表格里把“原地标记单独变量”单独列出来的原因——它才是面试中最稳妥的写法。4. 完整实操O(1) 空间的标准解法与代码实现4.1 标准写法的完整推导我把 O(1) 空间的标准写法拆成 5 个步骤每一布都解释清楚为什么。第一步先记录首行和首列本身是否需要清空。这一步可以理解为“先把地基加固再开始动工”。我们用两个变量first_row_zero首行是否有 0初始为 Falsefirst_col_zero首列是否有 0初始为 False分别遍历首行和首列如果发现 0 就置 True。这个记录必须在最开头完成因为在后面的标记阶段我们会主动把首行首列的部分格子改成 0那时候再判断就晚了信息已经被污染了。第二步用首行首列当标记黑板遍历内部区域。也就是从i 1到m-1、从j 1到n-1如果matrix[i][j] 0就把matrix[i][0] 0和matrix[0][j] 0。这一步不做任何清空操作只负责在“黑板”上写字。第三步根据黑板上的标记清空内部区域。再次遍历i从 1 到m-1、j从 1 到n-1如果matrix[i][0] 0 or matrix[0][j] 0就把matrix[i][j]置为 0。第四步单独处理首列。如果第一步记录的first_col_zero为 True就把第 0 列所有元素清成 0。第五步单独处理首行。如果第一步记录的first_row_zero为 True就把第 0 行所有元素清成 0。这里有个顺序细节值得解释第四步和第五步谁先谁后无所谓因为清空首列和清空首行用的都是第一步记录下来的独立变量不会互相影响。关键在于必须先清空内部区域再去处理首行首列本身。否则如果先清空首行首列再按首行首列清空内部那整个矩阵都会变成 0。4.2 Python 和 C 双版本代码下面是我在实际刷题和写面经时用过多次的最终版本可以直接抄。Python 版本def setZeroes(matrix): m, n len(matrix), len(matrix[0]) # 第一步记录首行首列是否含 0 first_row_zero False first_col_zero False for j in range(n): if matrix[0][j] 0: first_row_zero True break for i in range(m): if matrix[i][0] 0: first_col_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_col_zero: for i in range(m): matrix[i][0] 0 # 第五步处理首行 if first_row_zero: for j in range(n): matrix[0][j] 0C 版本class Solution { public: void setZeroes(vectorvectorint matrix) { int m matrix.size(); int n matrix[0].size(); bool firstRowZero false; bool firstColZero false; for (int j 0; j n; j) { if (matrix[0][j] 0) { firstRowZero true; break; } } for (int i 0; i m; i) { if (matrix[i][0] 0) { firstColZero 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 (firstColZero) { for (int i 0; i m; i) { matrix[i][0] 0; } } if (firstRowZero) { for (int j 0; j n; j) { matrix[0][j] 0; } } } };两个版本的逻辑完全一致面试时你用哪个都行。我个人建议至少把 Python 版本写熟练因为代码量更少和面试官解释思路时更直观。4.3 核心过程详解一个完整例子跑一遍光看代码可能还觉得抽象我拿一个具体矩阵从头到尾跑一遍你就彻底明白了。假设输入矩阵是[1, 1, 1] [1, 0, 1] [1, 1, 1]第一步检查首行第 0 行没有 0first_row_zero False检查首列第 0 列也没有 0first_col_zero False。第二步遍历内部区域从第 1 行第 1 列开始发现matrix[1][1] 0于是把matrix[1][0] 0和matrix[0][1] 0。此时矩阵变成[1, 0, 1] [0, 0, 1] [1, 1, 1]注意这里我们并没有在第二步就直接把第 1 行整行清成 0这是正确的。因为如果在标记阶段就顺手清空会破坏后续遍历时的判断。第三步再次遍历内部区域。matrix[1][0]现在已经是 0 了所以第 1 行的matrix[1][1]和matrix[1][2]都被清成 0。同时matrix[0][1]是 0所以第 1 列的matrix[2][1]也被清成 0。最终矩阵变成[1, 0, 1] [0, 0, 0] [1, 0, 1]第四步首列不需要单独处理first_col_zero为 False。但注意首列的第 1 行已经被我们标记成 0 了它会被保留下来——这没问题因为矩阵里第 1 行确实该清成 0。但首列其他格子比如matrix[2][0]没有被清成 0这也是对的。第五步首行也不需要单独处理。最终结果就是[1, 0, 1] [0, 0, 0] [1, 0, 1]手动验证一下原来只有matrix[1][1]是 0所以第 1 行整行变 0第 1 列整列变 0。结果正好符合。4.4 为什么第一步要先记录首行首列这一步可能是整个代码里最容易被忽略但又最关键的地方。如果我们不先记录first_row_zero和first_col_zero而是直接进入第二步做标记那么标记阶段会把matrix[0][j]改写成 0当内部某列有 0 时。例如[0, 1, 1] [1, 1, 1] [1, 1, 1]这个矩阵的首行本身就有 0。如果跳过第一步第二步遍历内部区域后会因为matrix[0][j]被改动而丢失“首行原本就含 0”这个信息。等到最后统一处理首行时你可能会认为首行不需要清空那就错了。所以第一步的本质是在工作开始前把两个“边界变量”的状态保存到外部变量里避免标记操作污染信息来源。这一步类似你在修改数据库之前先备份一份配置。5. 实战踩坑记录我见过的 5 个典型错误5.1 错误一标记阶段顺手清空矩阵有些初学者看到matrix[i][j] 0时会在标记的同时把这一行这一列立刻全部置 0。这会导致什么就是“信息的丢失”。比如矩阵[1, 0, 1] [1, 1, 1] [1, 1, 1]如果遍历到matrix[0][1]是 0 时你直接把第 0 行和第 1 列全清了那么矩阵会变成[0, 0, 0] [1, 0, 1] [1, 0, 1]然后你继续遍历看到后面很多位置因为被清成了 0又触发新的清行清列操作最后整个矩阵全是 0。这就是典型的“在收集信息的同时修改数据”导致的状态爆炸。正确做法是第一遍只做标记第二遍才做清空两阶段严格分离。5.2 错误二忘记处理首行首列本身很多网上流传的简洁版本只用了首行首列做标记但最后没有区分“首行首列原本是否有 0”。比如这样写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 # 最后再统一把首行首列全清成 0这种写法在首行首列原本就有 0 时是碰巧对的但如果首行首列原本没有 0而你把首行首列全清成 0就会误伤。所以无论怎么简化都必须处理这两个变量。5.3 错误三内部区域遍历范围写错标记阶段必须从i 1、j 1开始而不是从i 0、j 0开始。原因是首行首列本身是标记区不能既当黑板又当被标记对象。如果你从i 0开始遍历那么matrix[0][j]会被当作数据区的 0 来处理然后你又把它当作标记位的 0 来读等于“自己改自己”逻辑混乱。我在面试模拟时见过不少人写for i in range(m)然后内部再判断if i ! 0这样也能过但代码更啰嗦容易出错。直接写range(1, m)最干净。5.4 错误四Python 里误用二维列表乘法这个不完全是题目本身的坑但 Python 新手经常踩。比如想初始化一个全是 1 的矩阵有人会写matrix [[1] * n] * m。这在 Python 里会创建一个包含 m 个相同引用的列表你修改matrix[0][0]会发现matrix[1][0]也跟着变了。如果你用这种方式初始化测试用例还没开始写算法数据就已经错了。正确写法是matrix [[1] * n for _ in range(m)]这种初始化方式是 LeetCode 题目输入里默认的格式但你自己在本地测试时千万别写错。5.5 错误五变量名误导导致逻辑错乱在 O(1) 解法里matrix[i][0]和matrix[0][j]承担了双重角色既是矩阵的真实数据也是标记位。如果变量名起得不好很容易在代码里把“标记”和“数据”混为一谈。我见过有人把标记阶段写成if matrix[i][j] 0: matrix[0][j] 1也就是用 1 来标记而不是用 0。这乍一看好像没啥问题但别忘了题目要求清空后是 0你用 1 当标记就意味着原本为 0 的位置后面会被 1 覆盖完全不符合题目要求。所以标记值必须用 0。6. 面试扩展如果面试官继续往下追问6.1 变体一能否只用单个变量完成 O(1) 空间标准解用了两个变量first_row_zero和first_col_zero。有更极致的写法只用first_row_zero一个变量配上对首列的特殊处理。思路是把首列当作“行标记”数组首行当作“列标记”数组首行的第 0 个元素即matrix[0][0]兼作首列的标记然后单独用一个变量记录首行是否含 0。这样写确实可以再省一个变量但代码的可读性会明显下降。我个人建议面试中不要为了炫技而选择这种写法除非面试官明确要求你只用一个额外变量。更稳定的做法是用两个变量思路清晰、不易出错。6.2 变体二如果矩阵特别稀疏或者特别密集怎么办如果矩阵里 0 的数量特别少其实可以换一种思路先收集所有 0 的坐标再去清行清列。虽然这需要 O(k) 的额外空间k 是 0 的个数但在 0 很少时会比 O(mn) 更高效。不过在极端情况下比如矩阵全是 0k m×n这种办法就退化成最差方案了。日常刷题和面试中直接用 O(1) 的最优解就行不需要纠结这种变体。6.3 变体三相关题型推荐如果你把这题吃透了可以顺手刷几个相关题型巩固。第一个是 LeetCode 289 生命游戏它也是用原地技巧在矩阵里保存新旧两种状态需要在原矩阵上通过编码方式记录信息思路和矩阵置零有异曲同工之妙。第二个是 LeetCode 48 旋转图像考察的是顺时针旋转矩阵的原地变换也是矩阵下标的经典操作。第三个是 LeetCode 54 螺旋矩阵虽然不涉及原地标记但对二维数组索引的掌控要求极高属于打通矩阵类题目的必经之路。我自己刷题的经验是矩阵类题目不怕难怕的是你只会背题。把“标记-清空”两阶段分离、利用首行首列做存储这两个套路理解透很多看起来无从下手的矩阵题都会变成套路题。7. 小结与经验心得这题在 LeetCode 热门 100 题里地位很高也是很多公司笔试面试的原题。为什么它能成为经典因为它在极其简单的题目描述下藏了一个很核心的算法思想——空间不够用时能不能在原始数据上做标记。我在实际刷题时最大的体会是很多题目卡住不是因为不懂算法而是因为“舍不得破坏原数组”。其实原地操作的核心不在于“不能破坏数据”而在于“破坏之后还能从标记里恢复出你想知道的信息”。矩阵置零告诉我们即使原数据被改写了只要保留住关键的分支判断信息后续依然可以把正确的答案算出来。最后再分享一个实用技巧刷这类题目时建议先用较小的测试用例手动画一遍过程比如 3×3、3×4看每一步的输出是否符合预期。很多人觉得 LeetCode 题解看懂了就过了但其实动手画一遍、跑一遍对理解信息流向的帮助远大于读十篇题解。矩阵置零这题尤其如此——你只要把一个 3×3 的例子完整走一遍所有关于“为什么倒着遍历”“为什么先记录首行首列”的疑问都会瞬间消失。希望这篇能帮你把矩阵置零彻底拿下下次再见到它直接 5 分钟写出 O(1) 空间的最优解。