矩阵置零LeetCode热题100：从暴力到原地标记的O(1)空间解法全解析

刷到LeetCode热题100的第73题矩阵置零时很多人第一反应是这题也太简单了吧遍历一遍矩阵碰到0就把对应行和列全打成0完事。但真上手写第一版代码十有八九会翻车——因为边遍历边置零会污染后续判断扫着扫着整个矩阵就全零了。这道题在LeetCode热题100里属于典型的看着简单做起来处处是坑的题目而且它考察的空间优化思路在面试里非常容易被追问。这篇文章我按自己的刷题经验把从暴力解法到原地标记法的完整演进过程、边界条件的处理细节、以及面试官大概率会追问的进阶方向都梳理一遍适合刚开始刷热题100的读者也适合准备面试想把这题答透的朋友。1. 为什么边遍历边置零是大多数人的第一版错误答案1.1 题目到底在说什么先对齐一下题意。给你一个 m 行 n 列的矩阵只要某个格子里的值是 0就要把这个格子所在的整行、整列全部改成 0。看起来规则非常直白没有任何绕弯的地方。LeetCode给的难度是Medium但实际上它的算法思路本身不复杂真正的难点在于空间复杂度的限制——大部分中文题解里都强调原地操作也就是除了原矩阵之外最多只能用常数级别的额外空间。举个例子给你这样一个3x3矩阵1 1 1 1 0 1 1 1 1期望输出是1 0 1 0 0 0 1 0 1只有中间那个0结果它所在的行和列全被清零了而四个角上的1幸存了下来。这个例子是最基础的情况真正的魔鬼藏在那些第一行或第一列本身就有0的测试用例里这个我后面会花一大段来讲。1.2 第一版代码的翻车现场大部分人第一次写这题思路是这样的遍历整个矩阵一旦发现某个位置是0就把这一整行和这一整列都改成0。这个方案看起来很符合直觉但问题立刻就会出现。还是用刚才那个矩阵举例遍历到第1行第1列从0开始索引发现是0于是把整个第1行和第1列都改成了0。接着继续往后遍历走到原本是1、但现在已经被改成0的位置比如 (1,2)它现在也是0了于是代码又跑去把第2列整列置零。就这样原本不需要修改的位置也会被连锁反应带进去最终输出一个全零矩阵直接Wrong Answer。这个问题的本质是置零操作和判断操作在同一轮循环里发生数据源被自己修改了导致判断失真。这是所有原地修改类题目都会遇到的经典冲突不只是矩阵置零。做这类题时心里要有一根弦——如果你想在遍历过程中依赖某个值做判断那就绝对不能在判断完之前去改它要么先记录下来回头再改要么用额外的空间把原状态保存起来。1.3 暴力解法其实也是了解数据流的入门最简单的暴力解法是复制一个一模一样的矩阵B然后在原矩阵A上遍历找0每找到一个是0的位置就把B里对应的整行和整列置零最后再把B复制回A。时间上要扫描矩阵若干次空间上是 O(mn)因为要额外开一个和原矩阵一样大的空间。这种方法在LeetCode上能通过但不是我们刷热题100想要的效果因为面试官一定会追问你能不能把空间复杂度降下来。理解暴力解法的意义在于它清楚地展示了这个问题的两个阶段探测阶段和回写阶段。探测阶段不动原数据只收集哪些行、哪些列需要被置零这个信息回写阶段才真正动手修改。所有更优的解法本质上都是在优化信息记录这件事的存储方式。2. 从记账数组到零额外空间两条路线的完整推演2.1 用两个一维数组做标记O(mn)的过渡方案既然复制整个矩阵太浪费空间自然会想到一个优化我不需要复制原矩阵只需要记录哪些行、哪些列需要被清空。用两个布尔数组rowFlag[i] 表示第i行是否包含0colFlag[j] 表示第j列是否包含0。第一遍遍历矩阵碰到0时只更新这两个flag数组不动原矩阵。第二遍再遍历矩阵只要当前位置的行flag或列flag为true就把这个位置修改为0。这个方案的空间复杂度是 O(mn)比O(mn)前进了一大步而且代码极好写class Solution { public void setZeroes(int[][] matrix) { int m matrix.length, n matrix[0].length; boolean[] rowFlag new boolean[m]; boolean[] colFlag new boolean[n]; for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 0) { rowFlag[i] true; colFlag[j] true; } } } for (int i 0; i m; i) { for (int j 0; j n; j) { if (rowFlag[i] || colFlag[j]) { matrix[i][j] 0; } } } } }为什么这个方案是安全的因为第一批遍历只是收集信息完全没有改动任何数据所以不存在污染问题。这其实就是工程上最常见的先标记后统一处理思想和你写代码时先把所有日志打出来、最后再统一分析错误是一样的道理。2.2 核心跃迁把标记信息存进哪里才不算额外空间面试官继续追问能不能连 O(mn) 的空间都不要这时候要换个思路。既然矩阵本身有那么多格子空着为什么不能把标记信息直接存在矩阵里你可能会说把信息存在原矩阵里不就污染数据了吗没错但关键在于不是所有格子都需要保留原始值。比如我们需要知道第1行是否包含0如果直接把矩阵[1][0]这个格子当作标记位把它改成0那第1行原本的信息就丢了。但这里有个非常巧妙的洞见——我们需要保留的信息本质上只有两类这个格子原本的值和它所在行列是否需要被清空。如果我们把标记放在一个反正最后也要被清空的位置上那就不存在信息丢失了。疯狂的想法出现了用矩阵自身的第一行和第一列作为标记区域。第i行是否需要置零记录在 matrix[i][0] 里第j列是否需要置零记录在 matrix[0][j] 里。因为不管怎样如果第i行需要置零那么 matrix[i][0] 这个格子最后一定是0所以提前把它改成0没有任何问题——它不需要保留原值。等一下这里有一个致命细节matrix[0][0] 在标记体系里同时是第一行的列标记和第一行的行标记一个人干两份活没法同时表示第一行有0和第一列有0。所以第一行和第一列不能完全按照同样的逻辑处理必须单独为它们留出两个布尔变量先保存它们的原始状态。这是原地标记法最核心、也最容易犯错的地方。3. 所有坑都集中在第一行和第一列状态记录与处理顺序3.1 两个布尔变量的意义先明确一个问题为什么需要单独记录第一行和第一列的原始状态因为在用第一行第一列做标记的方案里遍历过程中我们会修改 matrix[0][j] 和 matrix[i][0]。一旦修改原来的值就丢了。如果后面再做判断时需要知道第一行是不是原本就有0就再也查不到了。所以必须先动手记录这两份状态。这里有个面试加分小细节很多人只用两个 bool 分别记录最后处理的时候再分别判断这当然是对的。但也有一种更节省代码的写法先把第一行/第一列里是否有0记录下来再统一处理逻辑上更清晰面试讲起来也更容易解释。3.2 处理顺序的先后决定了代码对不对原地标记法的完整流程是这样的先扫描第一行记录 firstRowHasZero。再扫描第一列记录 firstColHasZero。从第二行第二列开始遍历矩阵的剩余部分如果某个格子是0就把它所在行的标记位 matrix[i][0] 置为0所在列的标记位 matrix[0][j] 置为0。再次从第二行第二列遍历检查每个格子的行标记和列标记只要有一个是0就把该格子置为0。最后根据 firstRowHasZero 决定是否把第一行整行清零根据 firstColHasZero 决定是否把第一列整列清零。为什么第3步要从 (1,1) 开始而不是从 (0,0) 开始因为如果从 (0,0) 开始遍历过程中会把 matrix[0][j] 和 matrix[i][0] 提前改掉这本身没问题因为标记本来就是要改的但问题在于如果你在遍历的时候把标记区域混进了数据区域那么你最开始保存的 firstRowHasZero 和 firstColHasZero 的含义就会被破坏。举个例子如果原始矩阵第一行本来没有0但在遍历 (1,1) 位置发现0时代码执行了 matrix[0][1] 0接着遍历到 (0,1) 时发现这个格子是0被标记改出来的0就会误判第一行原本有0最终第一行被错误地清零。所以第3步和第4步都只能遍历下标从1开始的子矩阵。先处理数据区域最后才碰标记区域本身这样标记位的0不会反过去污染哪些格子原本是0的判断。3.3 完整实现代码class Solution { public void setZeroes(int[][] matrix) { int m matrix.length, n matrix[0].length; boolean firstRowHasZero false; boolean firstColHasZero false; // 1. 记录第一行和第一列是否原本就有0 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; } } // 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. 根据标记把剩余区域中需要置零的位置改为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; } } } // 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; } } } }这段代码在LeetCode上可以击败大多数提交时间 O(mn)空间 O(1)已经做到了理论最优。面试时能把这份代码背后的三步走讲清楚比直接默写出来值钱得多。3.4 最常见的三种写错方式我见过很多人刷这题犯的错误无外乎这三类。提前帮你排雷第一种忘记保存第一行/第一列的初始状态。最后一步直接遍历第一行和第一列想当然地看到0就整行清零但此时第一行和第一列的值已经被第二步标记过程污染了结果就是第一行原本没有0却因为标记位被改成了0最终整行被错误清零。第二种处理顺序写反了。先置零了剩余区域的行列再回头用行列去判断哪些格子要清空。这样后续判断时原本是1的格子也会因为行列标记而变成0最终多清空一大片。我见过有人提交之后发现输出矩阵莫名其妙全是0基本都是这个原因。第三种把遍历范围写成了从0开始。也就是第二步和第三步里的 i 和 j 从0而不是从1开始。前面分析过这会用标记产生的0去污染哪些位置原本是0的判断相当于用错误的输入在错误的时间做了错误的修改。这三种错误本质上都是一件事标记区与数据区混在一起判断时区分不了原生的0和标记产生的0。想明白这个内核你就能在写代码时主动避开它们。4. 面试追问环节从能AC到答得漂亮4.1 位运算标记当矩阵规模足够小时的花活有时候面试官为了看你的知识面会问能不能在一次遍历内完成或者问如果你明确知道矩阵的行数或列数很小比如最多只有32行或32列能不能再省一点这时候可以抛出一个补充方案用整型变量的位bit来做标记。一个 int 有32位每一位代表一行或一列。第一遍遍历发现 (i,j) 是0就执行 rowMask | (1 i) 和 colMask | (1 j)把第 i 行和第 j 列对应的位标记成1。第二遍遍历检查 ((rowMask i) 1) 或 ((colMask j) 1) 是否为1是就置零。空间只需要两个 int比 O(mn) 数组又省了一截而且代码非常紧凑class Solution { public void setZeroes(int[][] matrix) { int m matrix.length, n matrix[0].length; int rowMask 0, colMask 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 0) { rowMask | (1 i); colMask | (1 j); } } } for (int i 0; i m; i) { for (int j 0; j n; j) { if (((rowMask i) 1) 1 || ((colMask j) 1) 1) { matrix[i][j] 0; } } } } }注意这个方案的适用前提行数和列数都不能超过31如果是Java的int。如果题目改成 m、n 最大可以到10^5位运算就会越界这时还是回到布尔数组方案。所以在面试中提及位运算时一定要主动说明使用条件和限制这反而能体现你对问题边界的理解。4.2 为什么说这题的工程思想比代码本身更重要矩阵置零这道题放在日常工作里其实有很强的原型意义。比如在处理图像数据时你要把图片上某些脏点所在的行列全部清除比如在电子表格里批量隐藏所有含特定标记的行和列甚至在做数据库批处理时要根据某些行字段的异常值批量把整行整列的状态更新掉。这些场景的共同套路都是两阶段法先收集需要变更的元信息再统一执行变更。这种思想比任何一行代码都值钱。你在实际项目中写的批量任务如果边遍历边改大概率会出和这道题一模一样的bug后面的数据因为前面的修改而失真。多刷几道这种题目你会慢慢形成条件反射遇到需要根据集合中某些元素来决定批量修改的需求时第一反应就是先标记后处理。4.3 与热题100里其他矩阵题的横向对比LeetCode热题100里还有几道矩阵类的题目思路上有互相呼应的关系。比如第54题螺旋矩阵考的是遍历顺序的模拟第289题生命游戏同样是原地操作、需要同时更新所有格子的经典题它给的技巧也是把新旧状态编码进同一个格子用额外的标记位来避免数据污染。矩阵置零里第一行第一列当标记区的思想和生命游戏里用个位存下一状态、十位存当前状态的做法本质上都是用额外的维度编码信息。所以刷题的时候不要只刷一道最好把一个类型的多道题放在一起做横向比较。你会发现很多看似不同的题底层都是同一套思想在反复变形。掌握了这个变形能力你做新题时的破题速度会快很多。我个人在实际面试中会把这道题当作空间复杂度优化的入门题来讲因为它非常直观地展示了从 O(mn) 到 O(mn) 再到 O(1) 的演进路径。刷题时我建议你也按照这个顺序去摸索不要直接抄最优答案先自己写一版暴力的再优化一版数组标记的最后再看原地标记法为什么能成立。走完这三步你对原地修改这一大类题目的理解会上一个台阶。最后再分享一个小技巧写矩阵类代码的时候尤其涉及边界下标时强烈建议在本地调试时每一步都打印出矩阵的中间状态。你可以把两个 for 循环的当前矩阵输出出来一眼就能看出标记过程有没有污染数据。这比自己干瞪眼盯代码高效得多。