提到零矩阵很多人第一反应是线性代数课本里那个全是 0 的矩阵。但如果你最近在刷题大概率会看到另一道叫“零矩阵”的题目给定一个 m×n 的矩阵如果某个元素是 0就把这个元素所在的行和列全部变成 0。我第一次在面试里碰到这道题时脑子里还全是数学课本的画面后来才明白这个词在算法语境下其实是个操作题。这篇文章准备把零矩阵从定义、思路、代码到工程场景一次聊透尤其是最常考的原地修改方案我会把坑和细节摊开讲让你看完就能直接上手写。1. 零矩阵到底要解决什么问题1.1 数学上的零矩阵和算法题里的零矩阵先澄清一个概念。数学里的零矩阵指的是所有元素都为 0 的矩阵记作 (0_{m \times n})它是矩阵加法里的单位元任何一个矩阵加上零矩阵都等于它自己。同时零矩阵乘以任何矩阵结果还是零矩阵所以它也是矩阵乘法里的“零因子”。这些性质在线性代数里很干净但放到算法题里情况就不一样了。算法题里的“零矩阵”其实有个更常见的名字矩阵置零。问题是给你一个原始矩阵你只能根据原始状态中值为 0 的位置把它所在的行和列全部置为 0。这里的关键词是“原始状态”。如果你一边扫描一边置零前面刚把某一行变成 0后面的判断就会受到干扰最后整个矩阵可能全变成 0。所以这道题真正的难度不在于“怎么把 0 扩散开”而在于“怎么在修改之后还记住原来的 0 在哪里”。很多人第一眼看到这个题目会觉得非常简单遍历一遍遇到 0 就把它所在的行和列都改掉。但你要知道LeetCode 这道题还有一个隐藏要求空间复杂度尽量低最好做到 O(1)。这直接把那些“复制一份矩阵”“开两个布尔数组”的方案都打上了折扣。面试官想看到的不是你会不会暴力解而是你懂不懂怎么复用已有空间。1.2 为什么不能直接开新矩阵这道题最简单的思路是复制一个一模一样的矩阵然后扫描原始矩阵里的 0在备份矩阵上把对应行列置零。这样确实能保证判断不受影响代码也几乎不可能写错。但问题也很明显额外空间是 O(m×n)如果矩阵是 10000×10000你等于内存占用翻了一倍这在工程里是完全不能接受的。有人说那我只记录 0 的坐标空间复杂度就是 O(K)K 是 0 的个数。这个思路没错但最坏情况下矩阵全是 0K 又是 O(m×n)和复制矩阵没有本质区别。而且如果你存的是一个坐标列表后续还要遍历每个坐标去标记行、列重复置零操作会很多时间上也不划算。所以这道题的核心矛盾就变成了我要么用两个长度分别为 m 和 n 的数组记录哪些行、哪些列需要变 0这是标准的 O(mn) 空间做法要么再进一步把这两个数组“塞”进矩阵自己的第一行和第一列里做到真正的 O(1) 空间。这个从 O(mn) 到 O(1) 的跳跃才是整个题目最精彩的地方。2. 从最直观的解法到空间优化2.1 暴力复制法最稳但最废内存先看最直接的方案。我复制一份原始矩阵然后遍历这份备份。只要发现某个位置是 0我就在原矩阵上把这一整行和这一整列都改成 0。这个做法最大的优点是逻辑简单不用考虑标记覆盖的问题适合在时间紧张、或者题目没有空间限制时先用它保底。def set_zeroes_copy(matrix): m, n len(matrix), len(matrix[0]) backup [row[:] for row in matrix] for i in range(m): for j in range(n): if backup[i][j] 0: # 行置零 for k in range(n): matrix[i][k] 0 # 列置零 for k in range(m): matrix[k][j] 0这个代码的时间复杂度是多少最坏情况下每个位置都是 0那么每遇到一个 0 都要把整行整列走一遍总共是 O(m×n×(mn))。虽然在实际数据里不会这么极端但这个上界确实不好看。空间复杂度是 O(m×n)因为备份矩阵完整复制了一份。这种解法放在笔试里不会扣分但如果是面试面试官大概率会追问一句能不能不用额外空间如果你没准备就会卡住。所以我的建议是暴力法只用来验证思路最终还是要掌握更优的标记法。2.2 标记数组法空间降到 O(mn)既然人脑记不住那么多位置那就让数组帮我们记。我们开两个布尔数组一个长度为 m记录哪些行需要置零一个长度为 n记录哪些列需要置零。第一遍扫描矩阵遇到 0 就把对应的 row_flag[i] 和 col_flag[j] 设为 True第二遍再遍历矩阵只要当前行或当前列被标记就把这个位置改成 0。def set_zeroes_mark(matrix): m, n len(matrix), len(matrix[0]) row_flag [False] * m col_flag [False] * n for i in range(m): for j in range(n): if matrix[i][j] 0: row_flag[i] True col_flag[j] True for i in range(m): for j in range(n): if row_flag[i] or col_flag[j]: matrix[i][j] 0这个方案是我最推荐给初学者的方案。它的时间复杂度只有 O(m×n)比暴力复制法稳定得多空间复杂度 O(mn)。而且思路非常符合直觉先把“哪些行、哪些列要变 0”记录下来再统一执行修改。这比一边改一边判断要安全得多。你可能觉得 O(mn) 还不够好因为题目希望 O(1)。别急标记数组法最大的价值是帮我们建立了一个“先记录、后修改”的框架。理解了它再看原地标记法就会觉得顺理成章。2.3 原地 O(1) 的核心用第一行第一列当标记位O(1) 空间的关键就在于把两个标记数组“藏”进矩阵自身的第一行和第一列。因为第一行和第一列本来也是矩阵的一部分我们可以用 matrix[i][0] 表示第 i 行是否需要置零用 matrix[0][j] 表示第 j 列是否需要置零。这样就不需要额外开数组了。但这里有个问题第一行和第一列本身也可能被修改牵一发而动全身。如果我们在标记过程中把 matrix[0][0] 改了就会丢失第一行和第一列是否需要置零的信息。所以必须先记录两个布尔值第一行原本是否包含 0第一列原本是否包含 0。这两个布尔变量就是唯一的额外空间常数级算 O(1)。具体分三步走第一步扫描原始矩阵记录首行首列是否有 0第二步从第二行第二列开始扫描遇到内部有 0就把该位置所在行的首列元素和所在列的首行元素标记为 0第三步根据这些标记把内部元素置零再根据第一步记录的布尔值还原首行首列。这个逻辑听起来绕但只要理解了“把标记存到边界上”这个想法代码反而很好写。我在下一节会给出完整实现并且逐个坑都讲清楚。3. 原地置零的细节与坑3.1 完整代码实现直接上代码我用 Python 写语言无关核心逻辑在任何语言里都一样。def set_zeroes_o1(matrix): m, n len(matrix), len(matrix[0]) # 1. 先记录第一行和第一列原本是否有 0 first_row_has_zero False first_col_has_zero False for j in range(n): if matrix[0][j] 0: first_row_has_zero True for i in range(m): if matrix[i][0] 0: first_col_has_zero True # 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 # 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] 0这段代码整体上就是“两步走”的进阶版先用布尔变量锁住首行首列的信息再用边界元素代替布尔数组。注意第 3 步中判断条件用的是 matrix[i][0] 和 matrix[0][j]这两个位置已经被当成了标记所以扫描时一定要避开第一行第一列否则你会发现原本的标记也被当成内部元素置零了。3.2 为什么你写的原地版本总报错我见过很多人在面试现场写这个解法十次里有八次会踩进同一个坑最后处理第一行第一列时没用一开始保存的布尔变量而是直接遍历 matrix[i][0] 和 matrix[0][j] 来判断。这么做的严重后果是假如 matrix[0][0] 本身就是 0那么第一行第一列在标记阶段会被当成一个普通位置处理导致你无法区分“首行首列原本就有 0”和“首行首列被标记成了 0”这两种情况最终把整个矩阵清成一片空白。另一个高频错误是顺序问题。有些同学会在第二步扫描内部元素的同时顺手把第一行和第一列的元素也处理了。比如二维循环写成 range(m) 和 range(n)没有从 1 开始。一旦你先把 matrix[0][j] 改了后面再用它判断第 j 列是否需要置零时信息就已经丢了。这个问题的本质就是标记和修改不能用同一份数据同时进行必须先完成所有标记再执行修改。还有一个隐藏坑是边界条件。如果矩阵只有一行或者一列内部循环 range(1, m) 或 range(1, n) 可能直接跳过这时你的标记步骤形同虚设。解决办法是依赖第一步的布尔变量当 m 1 时first_col_has_zero 就是在遍历第一列实际上也就是在遍历整行当 n 1 时同理。所以在写边界条件时要确保第一步遍历的是整行整列而不是 range(1, ...)。3.3 用一个例子走一遍完整流程我们拿一个 3×3 矩阵来手动推演1 0 3 4 5 6 7 8 9第一步扫描第一行发现 matrix[0][1] 0所以 first_row_has_zero True扫描第一列matrix[0][0] 1matrix[1][0] 4matrix[2][0] 7都没有 0所以 first_col_has_zero False。第二步从第 1 行第 1 列开始也就是数字 5 的位置扫描内部元素只有 (0,1) 有 0但它在第一行属于边界不会进入内部的 range(1,m) 和 range(1,n)。所以内部元素没有发现 0marker 阶段不会改变任何边界值。第三步根据标记置零内部元素。因为 matrix[1][0] 和 matrix[0][1] 都不是 0matrix[0][1] 虽然是 0但这是边界标记内部元素判断时它属于“第一行”不过在这个例子里内部元素 5 的所在列 j1 对应的 matrix[0][1] 已经是 0所以 matrix[1][1]、matrix[2][1] 都会被置零。同时matrix[1][0] 不是 0matrix[0][1] 是 0因此第 1 列整个都会变 0。最终得到1 0 3 4 0 6 7 0 9第四步因为 first_row_has_zero True所以把第一行整行置零0 0 0 4 0 6 7 0 9这个结果是对的原始矩阵中 (0,1) 是 0所以第 0 行和第 1 列都应该变成 0。你会发现第四步的顺序放到最后特别重要如果提前把第一行置零那么 matrix[0][j] 这个标记信息就被冲掉了。4. 零矩阵的工程应用与扩展思考4.1 图像处理里的“行清空”操作零矩阵的操作逻辑在图像处理里特别常见。你想想一张灰度图在计算机里就是一个矩阵黑色像素的值是 0白色像素的值很大。有时候我们需要“把黑色像素所在的整行整列都清掉”比如在做文档扫描时要抹掉表格线或者在抠图后想清除某些异常噪声区域。这和“矩阵置零”就是同一个操作。实际工程里我们通常不会真的把整行整列都遍历一遍去赋值。更常见的做法是用“行投影”和“列投影”来加速先统计每一行是否有 0每一列是否有 0然后直接按行、按列操作。这其实就是标记数组法的工程版。如果图像特别大你还会用指针或者视图操作来避免复制整份数据这和算法题里 O(1) 空间的诉求不谋而合。另外零矩阵的概念也经常出现在稀疏矩阵处理中。一个矩阵如果大部分位置都是 0我们不会把每个 0 都存下来而是只存非零元素的位置和值。这时候如果某一行存在一个非零元素它就不是全零行反过来如果某一行全是 0在存储时就可以直接跳过节省大量内存。所以“识别全零行/列”这个任务本质上就是零矩阵判断的扩展。4.2 矩阵特别大的时候还能怎么优化算法题里的 m 和 n 一般不会太大但工程上你可能会遇到几十万行、几十万列的超大稀疏矩阵。这时候 O(m×n) 的遍历成本已经很感人更别提原地修改还要写回内存。我通常分两种思路来处理一是空间换时间二是并行化。空间换时间指的是先建立索引比如把非零元素的行号、列号分别存进两个哈希集合然后只需要处理这些行和列而不是全矩阵扫描。这样做的时间复杂度取决于非零元素个数而不是矩阵大小。对于稀疏矩阵收益非常明显。并行化就更大胆了。比如用 GPU 或者多线程每个线程负责一行先判断这一行是否需要置零再统一写入。但要注意并行写入同一个列时可能产生竞争所以更好的做法是分成两个阶段第一阶段并行计算每行每列是否有 0第二阶段并行按行置零必要时按列补写。这个套路和算法题里的“先标记再修改”完全一致只是扩展到了分布式环境。5. 常见问题与避坑速查5.1 一张表记住最容易犯的错我把平时做题和面试时最常碰到的错误整理成了表格你可以对照着自查。错误做法问题出在哪正确做法一边扫描一边置零修改后的 0 会继续扩散最后全矩阵变 0先标记所有需要置零的行列再统一处理用 matrix[0][0] 作为唯一标记无法区分首行首列原本有 0 和标记产生的 0提前用两个布尔变量保存首行首列状态第二步循环范围写成 range(m) / range(n)修改了第一行第一列破坏标记信息内部循环从 1 开始跳过边界最后忘记处理首行首列如果首行首列原本有 0不会全清空根据一开始的布尔变量最后单独处理认为 O(mn) 空间就是最优没有利用矩阵自身边界空间用第一行第一列代替数组实现 O(1)这张表基本覆盖了 80% 的 bug。很多同学看了题解觉得懂了一写就错原因就是没搞懂“为什么顺序这么重要”。记住一个口诀先记录再标记内部清零最后才处理边界。5.2 我踩过的坑和调试建议我第一次写原地版本的时候就在这一步翻车了我自认为想得挺明白把 matrix[0][j] 当作标记但忘记先保存 first_row_has_zero结果矩阵第一行本来没有 0却因为内部行列标记整个第一行被全部清成 0。我当时盯着输出看了半天完全不知道哪一步出了问题最后只好在纸上手动走一遍才找到原因。所以我后来调试这个题目时固定用一个小技巧打印每一轮的关键状态。你可以在标记阶段结束后专门打印一下第一行和第一列的值再打印内部矩阵一眼就能看出标记有没有被破坏。如果 matrix[0][0] 从非 0 变成了 0那一定是你在标记阶段不小心把首行首列也当内部元素处理了。如果你还没办法理解 O(1) 空间版本我的建议是先写一遍标记数组版本确保思路完全正确再尝试把它改写成边界复用版本。不要一上来就挑战 O(1)那样很容易被细节绕晕。毕竟面试的时候先给出一个清晰的 O(mn) 方案再主动提出优化到 O(1)比直接写错要加分得多。最后再分享一个小经验刷题碰到这种“矩阵修改类”题目核心心法就是“记录原始信息再原地修改”。零矩阵这道题只是把这种思想用到了极致你真的理解了它之后再去看“岛屿数量”“旋转图像”这类矩阵题也会觉得顺手很多。