矩阵置零这个题我第一次在刷题平台上看到时内心是有点不屑的两层循环遇到 0 就改行改列这不是有手就行可当我真的原地写起来才发现完全不是那么回事。题目本身很短给定一个m x n的整数矩阵只要某个位置是 0就把这一整行和这一整列全部变成 0并且要求原地修改不能用额外的矩阵去存结果。很多人在这一步就开始踩坑因为一旦你边扫边改后面的 0 到底是真的 0还是被改出来的 0根本说不清。这篇文章就用编号 73 的这道矩阵置零题做例子把常规解、原地标记解、边界处理和面试追问一次性说透适合正在刷算法题准备面试或者被“原地”两个字卡住的朋友。1. 题目到底在考什么不是双重循环而是状态管理1.1 两个示例先建立直觉先看最经典的示例。输入矩阵[ [1, 1, 1], [1, 0, 1], [1, 1, 1] ]中间位置是 0于是它所在的整行、整列都变成 0最终输出[ [1, 0, 1], [0, 0, 0], [1, 0, 1] ]再看一个稍微复杂的[ [0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5] ]这里有(0,0)和(0,3)两个 0所以第 0 行整体清 0第 0 列和第 3 列也整体清 0。结果长这样[ [0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]我一开始以为只要扫描到 0立刻把它所在的行和列全改了就行。但仔细想就会发现这样做等于在遍历过程中不断“制造新的 0”而这些新 0 又会触发新一轮修改最后常常把不需要清零的行列也清掉了。所以这类题目的第一关不是“会不会写循环”而是“能不能管理好修改前的状态”。1.2 “原地”这两个字才是难点本体很多人一眼就看出了辅助矩阵的解法复制一份matrix出来遍历副本把 0 的行列在原矩阵上清掉。这当然能通过但题目明确要求原地修改就是不想让你用O(mn)的额外空间。更准确地说这道题期望的空间复杂度是O(1)也就是允许你用几个临时变量但不能用第二块矩阵。所以我经常说这题真正的考点是“状态管理”。你需要把“哪些行、哪些列原本有 0”这件事先记下来等记录完整了再统一执行置零。记下来的过程叫“标记”执行的过程叫“结算”。把这两个阶段拆开问题就清晰了。2. 先用辅助数组把分数拿到O(mn) 空间的常规解2.1 扫描、记录、再执行三个步骤如果拿不到O(1)解至少先写出能跑的版本。最直观的做法是用两个数组或者两个集合一个记行一个记列。row_mark [False] * m col_mark [False] * n for i in range(m): for j in range(n): if matrix[i][j] 0: row_mark[i] True col_mark[j] True for i in range(m): for j in range(n): if row_mark[i] or col_mark[j]: matrix[i][j] 0这个解法的思想很简单第一遍只负责“找零并记账”第二遍根据账本统一“销账”。它的时间复杂度和空间复杂度分别是O(mn)和O(mn)。很多初学者写到这里就停了觉得能跑就行。2.2 为什么这套解法只能算热身问题是O(mn)的额外空间在这个题目背景下是“可以被优化掉”的。面试官看到你用row_mark col_mark大概率会追问一句能不能把额外的O(mn)也省掉原因在于你要标记的信息本质只有“某一行要不要清零、某一列要不要清零”一共mn个 yes/no。但矩阵本身已经有m*n个格子能不能让矩阵自己把这mn个标记记下来这就是原地标记法的出发点。千万不要觉得“反正能用就行”。刷题的意义之一就是逼自己理解为什么标准解法长那样。所以这一题我强烈建议看完辅助数组解法之后继续往下看原地标记法。3. 原地标记的底层逻辑把矩阵自身当公告牌3.1 公告牌的分配方案原地标记法的核心是把第一行和第一列当成一块“公告牌”。什么意思呢矩阵里有m*n个格子我们不需要为每一行、每一列单独准备一个变量只需要借用矩阵自己的格子第i行有没有 0看matrix[i][0]。第j列有没有 0看matrix[0][j]。但第一行和第一列本身也是有效数据把标记写在它们身上会覆盖原来的值。所以我们要在动手之前先把第一行和第一列“原本有没有 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))保存完之后第一行和第一列就可以被“弄脏”了。这时再扫描内部区域也就是从(1,1)到(m-1,n-1)一旦发现某个格子是 0就在它的行标记位和列标记位上做个记号。这个过程相当于每个格子发现自己有问题时不直接动手改整行整列而是跑到公告牌上插一面小旗。等所有人插完旗再统一看着公告牌执行。3.2 第一行第一列的“身份冲突”怎么解决有人可能会问为什么第一行和第一列的情况不能也记录在matrix[0][0]上那个位置正好是行标记和列标记的交点让它一肩挑不就行了这里的关键是“一个布尔量表达不了两个独立信息”。matrix[0][0]同时代表“第一行有没有 0”和“第一列有没有 0”但这两件事在逻辑上是独立的可能第一行有 0第一列没有也可能反过来。如果只用matrix[0][0]这一个格子信息一混合就分不清了。所以清晰版解法会刻意保存两个外部布尔变量first_row_has_zero和first_col_has_zero。这样一来负责的内容存放位置第一行原本是否有 0外部变量first_row_has_zero第一列原本是否有 0外部变量first_col_has_zero第i行i 1是否有 0matrix[i][0]第j列j 1是否有 0matrix[0][j]这四个信息来源互不干扰逻辑就干净了。3.3 扫描和置零为什么都要从 (1,1) 开始在清晰版里扫描和置零都刻意从(1,1)开始而不是从(0,0)开始。原因很简单第一行和第一列已经被指定为公告牌它们上面的值随时会因为其他位置的 0 而被改写。如果你扫描时把第一行、第一列的格子也当成“待判断的数据”那你读到的可能已经是被标记污染过的假 0同理如果你置零时把第一行、第一列也纳入常规区域就可能把公告牌上的标记提前擦掉。先处理内部区域最后再根据保存好的布尔变量处理第一行和第一列这样每一步的信息都是可靠的。这不是唯一的写法但这是最容易讲清楚、也最不容易写错的写法。4. 容易翻车的边界和顺序问题我踩过的三个坑4.1 义务先保存第一行与第一列的原始状态我第一次写原地版时忘了保存first_row_has_zero直接开始扫描结果一个普通的[[0,1],[3,4]]都跑不对。第一行本来有 0但扫描过程中第一行被当成了告示板等到最后想处理第一行时原始信息已经找不回来了。所以这个保存动作必须放在任何修改之前。哪怕后面把第一行、第一列改得再乱只要这两个布尔变量还在最后就能把第一行第一列恢复到正确状态。4.2 陷阱把标记位置和真实数据混在一起读还有一次我图省事想在一个双重循环里边扫描边置零。当时觉得遇到 0直接把整行整列都改了顺便把下一个位置也判断了不是很快吗结果就出问题了。举个例子[ [0, 1], [2, 3] ]如果从(0,0)开始边扫边改先把第 0 行和第 0 列置零矩阵会变成[ [0, 0], [0, 3] ]但程序还在继续遍历。当它扫描到(1,0)时发现这个格子现在是 0其实是我们刚才改出来的于是又触发一次置零把第 1 行也整行清 0。最终结果变成全 0这就错了。正确结果应该是[ [0, 0], [0, 3] ]教训很直接不能一边“判断原始状态”一边“就地修改”。必须分成两遍第一遍只插旗第二遍才动刀。4.3 边界空矩阵、单行、单列和单元素边界条件写不好代码再对也白搭。我建议写题时优先考虑这几种情况空矩阵matrix为空或者matrix[0]为空。代码一开始就要if not matrix or not matrix[0]: return。单行矩阵比如[[1, 0, 2]]此时first_col_has_zero仍然可以正常判断但内部区域range(1, m)是空的不会触发扫描需要靠最后的first_row_has_zero和first_col_has_zero来补。单列矩阵比如[[1], [0], [2]]原理同上只是内部区域range(1, n)是空的。单元素矩阵[[0]]或[[5]]。[[0]]会被正确清零[[5]]保持原样即可。这些问题本身不复杂但如果你刷题时没养成先考虑边界、再写主逻辑的习惯很容易在代码已经通过大半用例时被一个单行矩阵卡住。5. 完整代码实现清晰版与极致版对比5.1 清晰版两个布尔值零基础也能一眼看懂下面这个版本是我最推荐理解的写法。它用了两个额外布尔变量但仍然满足O(1)空间复杂度因为布尔变量数量固定不随矩阵大小增长。def setZeroes(matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[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第一遍结束后matrix[i][0]为 0 就说明第i行原本某个位置是 0matrix[0][j]为 0 就说明第j列原本某个位置是 0。第二遍只是把这些行、列在内部区域里的位置全部清掉。最后再根据两个布尔变量把公告牌区域自己修正过来。5.2 极致版只用一个额外变量把空间压到更紧凑如果你想把代码压缩得更极致可以把两个布尔变量收敛成一个。原理是让matrix[0][0]承担“第一行是否有 0”的标记额外用一个变量col0承担“第一列是否有 0”的标记。def setZeroes(matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) col0 1 # 1 表示第一列暂时不需要全清 # 第一遍扫描整个矩阵把标记写进第一行和第一列 for i in range(m): if matrix[i][0] 0: col0 0 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 0: matrix[i][0] 0这个版本最需要注意的是第一遍里的顺序col0必须在进入内层循环之前判断。因为如果第一行某个j 0的位置是 0内层循环会把matrix[0][0]改成 0如果此时再回头判断matrix[0][0]就会误以为第一列也需要清 0但第一列可能原本根本没有 0。第二遍选择从下往上遍历不是炫技而是让“当前行第一列是否已经根据col0被清 0”这个动作尽量往后放避免前面行被后面行的标记影响。虽然多数情况下顺序不容易踩坑但能写成更稳妥的方向还是尽量写稳妥。5.3 两版如何选择刷题阶段我建议先写清晰版。两个布尔变量的写法也许比极致版多了 1 个变量但逻辑边界非常清楚第一行、第一列的状态放在外部其他行、列的状态放在公告牌上。面试时如果要求严格可以说“额外空间是两个布尔值仍然属于O(1)常数空间”。如果你已经对清晰版了如指掌再练极致版会很有收获。极致版实际上是把“状态管理”的思想用到了极致连那两个布尔变量都想省掉。但日常笔试时间紧没必要为了省一个变量冒风险能跑对才是第一位的。6. 复杂度、验证用例和面试官常追问的变体6.1 时间复杂度和空间复杂度到底怎么算时间上两个版本都是扫描矩阵若干遍每一格被访问常数次所以都是O(mn)。空间上清晰版用了两个布尔变量极致版用一个布尔变量都不依赖m和n所以都是O(1)额外空间。很多人会误以为“用了变量就不是原地”其实原地算法说的是不能用与输入规模成正比的额外容器不是不能用临时变量。多两个bool完全没问题。6.2 五个拿来即用的验证用例遇到这种题别只盯着普通用例测建议把这几个边界直接丢进代码里跑用例输入期望结果验证重点全零矩阵[[0,0],[0,0]][[0,0],[0,0]]零不会引发死循环无零矩阵[[1,2],[3,4]][[1,2],[3,4]]没有 0 就不该改动第一行有零[[0,1,2],[4,5,6],[7,8,9]]第 0 行全 0其余行按列 0 清第一行布尔变量处理第一列有零[[1,2,3],[0,5,6],[7,8,9]]第 0 列全 0第 1 行全 0第一列布尔变量处理单元素矩阵[[5]]/[[0]][[5]]/[[0]]最小的边界规模另外单行、单列也值得单独测一遍特别是单行里第二列有 0 的情况最容易暴露公告牌被误覆盖的问题。6.3 这题背后的通用解题思想矩阵置零能教给我们的不只是那几行代码而是一种“先标记、后执行”的通用策略。很多跟数组、矩阵、链表相关的原地操作题本质上都是同一套思维先想清楚需要保留哪些原始信息再想办法把这些信息压缩到有限的位置里最后再原地改写。比如有的题会在数组里用正负号做标记有的题会借用链表头节点记录状态有的题会在矩阵元素上编码“旧状态新状态”。这些做法的共同点都是“不能被修改后的值骗了”。只要你在写代码之前先问自己一句“修改之前我需要记住哪些信息”这道题就已经解决了一大半。最后说点我个人刷题的习惯遇到这类原地修改的题我永远先拿一张纸左边写“要保留的原始信息”右边写“这些信息能藏在哪个位置”。矩阵置零就是一组经典范本搞懂它之后再看状态压缩、原地哈希、二维状态编码这类题都会顺手很多。不要只背答案要把“为什么用第一行第一列当标记”这件事讲清楚这才算真正过了这道题。