力扣hot100做到第18题迎面撞上“矩阵置零”。这道题在hot100里位置靠前属于“一刷必会、二刷要能默写”的经典原地修改题。题目本身不难懂给定一个 m x n 的矩阵如果某个元素是 0就把这一整行和整列全部置成 0。难点不在“怎么做对”而在“怎么用最省空间的方式做对”。很多人第一次写出来的解法是新开一个同样大小的矩阵做标记空间复杂度直接 O(mn)面试官看到这题大概率会追问一句“能不能原地完成”。这篇文章就把这道题的完整思路、三种层级的解法、Python 实现细节和容易踩的坑全部拆开讲清楚适合正在刷 hot100 的朋友也适合准备面试时需要快速掌握原地修改类题目套路的人。1. 题目理解与核心考点拆解1.1 这道题到底在考什么先说题目本身。输入是一个二维列表比如[[1,1,1],[1,0,1],[1,1,1]]中间那个 0 会把第二行和第二列全部变成 0结果就是[[1,0,1],[0,0,0],[1,0,1]]。如果矩阵里有多个 0每个 0 都会把自己的行和列“传染”成 0。注意这个传播是叠加的一个位置只要所在行或所在列存在任意一个原始 0它就要被置零哪怕它自己本来不是 0。力扣把这道题归为“数组/矩阵”类但真正的考点其实是两个第一个是原地修改in-place也就是不能额外开一个同等规模的矩阵来存标记第二个是如何避免“脏数据”污染判断过程。第二个考点才是大多数人的失分点。如果你一边遍历一边直接把整行整列改成 0那后面遍历到这个被改出来的 0 时会把原本不该变的行列也给改了连锁反应直接失控。所以必须先把“哪些行、哪些列需要置零”这个信息记录下来再统一动手改。1.2 为什么不能“看到 0 就现场改”我见过不少初学者写出这样的代码遍历到 matrix[i][j] 0立刻用一个循环把第 i 行和第 j 列全部置 0。跑用例时发现结果完全不对。原因很简单假设矩阵是[[0,1],[1,1]]第一个元素是 0你把第一行第一列都改成 0矩阵变成[[0,0],[0,1]]接着遍历到(0,1)发现它现在是 0 了于是又把第二列整个置 0矩阵变成[[0,0],[0,0]]。但正确答案其实是[[0,0],[0,1]]因为右下角那个 1 所在的行和列原本都没有 0。这就暴露了问题的本质置零操作产生的 0 和原始 0 在数值上无法区分。所以题干里“原地修改”的真正含义是要求你用某种方式把“原始 0 的位置信息”存下来而且最好别用 O(mn) 的额外空间。理解了这一点后面所有解法都是围绕“在哪存、怎么存”来展开的。1.3 从暴力到最优的三级跳这道题的空间复杂度有明确的三个台阶O(mn) - O(mn) - O(1)。第一级是新手解法开一个同尺寸的布尔矩阵记录哪些位置是 0然后二次遍历按标记置零代码最直白但空间最差。第二级稍微动点脑子既然置零是按“行”和“列”进行的就只需要记录需要置零的行号和列号两个集合各存 m 和 n 个布尔值空间降到 O(mn)。第三级才是这道题的精髓——把矩阵的第一行和第一列本身当作标记数组。既然反正这些位置最终可能被置零不如在置零前先让它们“兼职”记录信息这样连额外的数组都省了。下面逐一展开。2. 三种解法思路对比2.1 解法一双数组标记法最直觉的思路先看最直观的版本。遍历矩阵遇到 0 就把row_set加入 i、col_set加入 j最后再遍历一次只要 i 在 row_set 里或者 j 在 col_set 里就把当前位置置 0。这里用 Python 的 set 天然去重代码非常简洁def set_zeroes(matrix): m, n len(matrix), len(matrix[0]) rows, cols set(), set() for i in range(m): for j in range(n): if matrix[i][j] 0: rows.add(i) cols.add(j) for i in range(m): for j in range(n): if i in rows or j in cols: matrix[i][j] 0这个解法的优点是逻辑清晰两遍遍历都是 O(mn) 时间空间 O(mn)面试时作为“先给一个可行解”的铺垫非常合适。缺点也明显用了额外空间不是本题最想考察的答案。如果你只是为了 AC这个写法已经能过但如果你在准备面试面试官大概率会追问一句“能不能把空间压到 O(1)”2.2 解法二集合标记法代码最简洁的过渡方案其实上面的 set 版本已经就是集合标记法不需要再单独列一个。但有个更巧的变体不用 set用两个长度为 m 和 n 的布尔数组row_flag[i]表示第 i 行是否需要置零col_flag[j]表示第 j 列是否需要置零。遍历时把对应标记置 True第二遍遍历查标记。时间一样空间也是 O(mn)但比 set 省一点哈希开销。用 Python 写的话 set 版本更省事两者思路完全等价选一个你顺手的就行。这一级的核心思想是“把矩阵的信息压缩到两个一维结构里”因为真正需要记录的信息只有哪些行、哪些列要置零而不是每一个坐标。想明白这一步才能理解下一节为什么第一行第一列也能当标记用——它们本质上就是“免费”的两个一维数组。2.3 解法三原地 O(1) 标记法面试最优解现在进入正题。观察解法二的两个布尔数组它们的信息量其实很小row_flag有 m 个布尔值col_flag有 n 个布尔值。而矩阵本身的第一列有 m 个格子第一行有 n 个格子——容量完全够那能不能不用额外的数组直接把这些标记写进矩阵自己的第一行和第一列里具体做法先遍历整个矩阵跳过第一行第一列如果发现matrix[i][j] 0就在“标记区”打点把matrix[i][0]设为 0 表示第 i 行需要清理把matrix[0][j]设为 0 表示第 j 列需要清理。遍历结束后再根据这些标记把内部区域置零。但这里有个陷阱第一行和第一列本身也可能包含原始 0如果直接拿它们当标记这些原始 0 会和标记 0 混在一起导致第一行第一列的状态判断出错。所以必须在开始打标记之前先把第一行和第一列“原来有没有 0”这个信息单独记下来比如用两个布尔变量。完整代码下一节给出。这一解法的空间复杂度是真正的 O(1)只用了两个额外变量完美满足面试官“原地修改”的要求。时间复杂度依然是 O(mn)因为再怎么优化每个元素至少要被检查一遍。3. 最优解法的 Python 实现细节3.1 完整代码逐行拆解下面给出我推荐的主写法。它用两个布尔变量记录第一行和第一列的原始状态然后用矩阵的第一行第一列作为标记区逻辑比较直观不容易写错def set_zeroes(matrix): m, n len(matrix), len(matrix[0]) # 先记录第一行和第一列本身是否包含 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: for j in range(n): matrix[0][j] 0 if first_col_has_zero: for i in range(m): matrix[i][0] 0逐行解释一下这个代码的每一步在干什么。首先是first_row_has_zero和first_col_has_zero这两个布尔变量它们的生命周期贯穿整个函数是唯一允许存在的“额外空间”。如果矩阵是[[0,1,1],[1,1,1],[1,1,1]]第一行有 0所以first_row_has_zero为 True这个信息如果不提前记下来后面第一行会被当成标记区改得面目全非无从判断原始状态。第一遍扫描从(1,1)开始故意跳过第一行第一列。只要发现内部有 0就在对应行首和列首打标记。这里有个微妙的地方matrix[0][j]是标记第 j 列matrix[i][0]是标记第 i 行。这些标记会覆盖第一行第一列的原始值但没关系因为原始值已经用布尔变量保存了。第二遍扫描同样从(1,1)开始只根据标记清理内部千万不能把第一行第一列也带进去否则先改了第一行就会破坏后面列标记的判断。最后才处理第一行第一列按布尔变量恢复或置零。3.2 关键细节第一行第一列的“标记冲突”陷阱很多第一次写这个解法的人都会在同一个地方翻车他们先扫描标记然后直接二次遍历for i in range(m): for j in range(n)把凡是matrix[i][0] 0 or matrix[0][j] 0的位置都置零。结果发现整个矩阵可能全变成 0 了。问题出在遍历顺序。假设标记后matrix[0][1] 0表示第 1 列要置零。二次遍历时如果遍历到(0, 1)发现matrix[0][0]可能不是 0但matrix[0][1] 0于是把第一行第 1 列置 0。这本身没错但如果你遍历到(1, 1)时检查matrix[0][1]它已经被你改成 0 了——这就等于标记本身被覆盖后面的判断全部失效。所以二次遍历必须严格限制在range(1, m)和range(1, n)内部区域第一行第一列留到最后单独处理。这个“先内部后边框”的顺序是整道题最容易错的点建议把它当成公式记下来。3.3 为什么 col0 要单独用一个变量另一种常见的精简写法是只用一个col0变量用matrix[0][0]同时兼任“第一行是否有 0”的标记。代码长这样def set_zeroes(matrix): m, n len(matrix), len(matrix[0]) col0 False for i in range(m): if matrix[i][0] 0: col0 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 col0: matrix[i][0] 0这个写法更紧凑但理解门槛更高。关键在于第一列在标记时被matrix[i][0] 0反复覆盖原始的“第一列是否含 0”只能靠col0提前存住而第一行的状态则交给matrix[0][0]自己因为matrix[0][0]只在i 0时会被写其他行的标记不会碰它。二次遍历时从右下角倒着走从m-1到0这样处理第一行的标记matrix[0][j]时别的地方已经处理完了不会互相干扰。两个版本功能完全等价我建议新手先掌握两个布尔变量的版本理解透彻后再去看单变量精简版两种写法在面试中都算标准答案。4. 边界用例与常见错误排查4.1 边界情况速查表写这道题时下面这些用例你必须亲手跑一遍任何一个出了问题都说明你的代码还有漏洞。测试用例预期结果考察点[[0]][[0]]单元素矩阵mn1[[1]][[1]]无 0 情况[[0,1]][[0,0]]单行矩阵第一行本身有 0[[1],[0]][[1],[0]]单列矩阵第一列本身有 0[[1,1,1],[1,0,1],[1,1,1]][[1,0,1],[0,0,0],[1,0,1]]经典多行多列[[0,1,1],[1,1,1],[1,1,0]][[0,0,0],[0,1,0],[0,0,0]]第一行和最后一行有 0全 0 矩阵全 0所有行列都需置零单行单列的情况特别容易漏。比如[[0,1]]如果你的代码里first_row_has_zero any(matrix[0][j] 0 for j in range(n))只对n个元素做判断而后面内部区域的循环range(1, m)直接为空最后处理第一行时把它全部置 0这个结果是正确的。但如果实现时不小心把第一行的处理条件写成if matrix[0][0] 0而matrix[0][0]已经被标记区的列标记覆盖成了 0那即使第一行原本没有 0 也可能被误置零所以测试用例要覆盖到这种单行输入。4.2 我踩过的三个坑第一个坑是二次遍历时没有跳过第一行第一列。这个前面已经详细说了症状是矩阵大面积变成 0尤其在有多个 0 的时候特别明显。排查方法很简单把矩阵缩小到 3x3手动在纸上走一遍循环看标记值是怎么被覆盖的。第二个坑是 Python 里any生成器的误用。any(matrix[0][j] 0 for j in range(n))返回的是布尔值不是生成器对象这点没问题。但如果你写成any([matrix[0][j] 0 for j in range(n)])虽然结果一样却多构造了一个列表对 m 或 n 很大的矩阵来说白白浪费 O(n) 空间——这就违背了 O(1) 的初衷。用any加生成器表达式或者干脆手写 for 循环。第三个坑出现在测试环节刷题平台给的是List[List[int]]直接修改传入的 matrix 本身是允许的但如果你在函数开头写了matrix matrix.copy()那就不是原地修改了。另外 Python 里matrix[:] new_matrix这种整体赋值虽然会修改原对象但熟悉的人少容易在边界场景下标错不如老老实实在原矩阵上操作。4.3 如何用一段小脚本验证所有边界用例刷题时我习惯把边界用例揉进一个测试函数里每次改完代码直接跑一遍省得反复提交。你可以这样写def test_set_zeroes(): cases [ ([[0]], [[0]]), ([[1]], [[1]]), ([[0, 1]], [[0, 0]]), ([[1], [0]], [[1], [0]]), ([[1, 1, 1], [1, 0, 1], [1, 1, 1]], [[1, 0, 1], [0, 0, 0], [1, 0, 1]]), ([[0, 1, 1], [1, 1, 1], [1, 1, 0]], [[0, 0, 0], [0, 1, 0], [0, 0, 0]]), ] for matrix, expected in cases: set_zeroes(matrix) assert matrix expected, ffailed: {matrix} print(all passed) test_set_zeroes()注意cases里每一组都应该是独立的矩阵对象不能在测试里复用同一个变量否则上一个用例的结果会污染下一个。这种“把用例写在代码里”的习惯在面试时也很有用你可以直接现场跑给面试官看比嘴上解释更有说服力。5. 举一反三这类“原地修改标记”题的通用套路5.1 标记法的本质在数据区上叠加一层“元信息”矩阵置零这题做完之后你会发现它和很多题共用一个套路在不额外开大数组的前提下借用数据本身的一部分去记录元信息。最经典的两个类似例子是“生命游戏”和“寻找重复数”。力扣第 289 题“生命游戏”要求原地更新矩阵每个细胞的状态由周围 8 个格子的当前状态决定。如果一边遍历一边改后面的判断就会被污染和矩阵置零是一模一样的困境。它的解法是用中间状态来编码用2表示“原来活着但下一轮死”用-1表示“原来死了但下一轮活”。最终再次遍历按规则把中间状态转回 0 或 1。这里2和-1就是叠加在原数据上的“元信息”靠它们避免脏数据污染判断。另一个例子是寻找重复数题目限制只能用 O(1) 空间但数组本身可以被修改。解法之一是把数组当成“链表”利用元素值作为下标跳转访问过的位置打上负号标记发现某个位置已经是负的说明它被访问过两次。这也是典型的“用数据本身的符号位存标记”。做矩阵置零时如果把这一层想通你以后遇到“原地修改”的题就不会慌因为底层思路是一样的要么用额外的特殊值编码状态要么借一块不会被重复使用的区域当临时黑板。5.2 从刷题到工程什么时候真该用这种技巧面试时这种 O(1) 空间的解法确实是卖点但实际工程里要不要用我会认真掂量。在真实业务里矩阵置零最典型的场景是数据清洗比如一张用户行为表某一行某一列是空值或异常值需要把整行的相关指标全部置空。这种场景下数据量可能非常大但修改是持久化操作代码的可读性和可维护性远比省几个字节重要。用两个 set 记录行列号逻辑一目了然同事review不会皱眉硬写成 O(1) 的标记法半年后自己看都要想半天。反过来如果处理的是嵌入式设备或者极大规模矩阵的底层算法内存是硬约束那 O(1) 的原地标记法就有不可替代的价值。所以这道题的正确打开方式是刷题时掌握两种写法理解每种写法的适用场景而不是一律追求 O(1)。面试官真正想看的也不是“你写出了最优解”而是你能不能在几种解决方案之间做合理的权衡。5.3 还要不要继续深挖的变体如果你还有余力可以想想两个进阶变体。第一是“如果矩阵非常大大到第一行第一列不能随意覆盖怎么办”这时可以用位图或外部存储记录标记思路不变但实现细节完全不同。第二是“能不能一次遍历就完成置零”理论上可以结合前向标记但需要对行列状态做更精细的维护代码复杂度明显上升实际面试中基本不会要求。刷题到这里就可以刹车了把最核心的 O(1) 标记法练到闭眼能写比追各种花哨变体要有用得多。回到最开始的感受这道题之所以在 hot100 里站了一个位置就是因为它用最朴素的矩阵题外壳装了一个非常重要的算法思想原地修改时如何安全地存储中间状态。我第一次独立写对 O(1) 解法时那种“原来还能这样”的感觉到现在还记得。建议你把两个布尔变量的版本记牢再理解单变量精简版的倒序遍历然后自己动手在编辑器里跑一遍所有边界用例。矩阵置零这道关过了后面再遇到类似的原地标记题你会觉得轻松很多。