企业官网建设流程全解析

矩阵置零这个题，我第一次在刷题平台上看到时，内心是有点不屑的：两层循环，遇到 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(m+n) 空间的常规解

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(m+n)。很多初学者写到这里就停了，觉得能跑就行。

2.2 为什么这套解法只能算热身

问题是，O(m+n)的额外空间在这个题目背景下是“可以被优化掉”的。面试官看到你用row_mark + col_mark，大概率会追问一句：能不能把额外的O(m+n)也省掉？原因在于，你要标记的信息本质只有“某一行要不要清零、某一列要不要清零”，一共m+n个 yes/no。但矩阵本身已经有m*n个格子，能不能让矩阵自己把这m+n个标记记下来？这就是原地标记法的出发点。

千万不要觉得“反正能用就行”。刷题的意义之一，就是逼自己理解为什么标准解法长那样。所以这一题我强烈建议，看完辅助数组解法之后，继续往下看原地标记法。

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。这样一来：

这四个信息来源互不干扰，逻辑就干净了。

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行原本某个位置是 0；matrix[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 的情况，最容易暴露公告牌被误覆盖的问题。

6.3 这题背后的通用解题思想

矩阵置零能教给我们的，不只是那几行代码，而是一种“先标记、后执行”的通用策略。很多跟数组、矩阵、链表相关的原地操作题，本质上都是同一套思维：先想清楚需要保留哪些原始信息，再想办法把这些信息压缩到有限的位置里，最后再原地改写。

比如有的题会在数组里用正负号做标记，有的题会借用链表头节点记录状态，有的题会在矩阵元素上编码“旧状态+新状态”。这些做法的共同点都是“不能被修改后的值骗了”。只要你在写代码之前先问自己一句“修改之前，我需要记住哪些信息？”，这道题就已经解决了一大半。

最后说点我个人刷题的习惯：遇到这类原地修改的题，我永远先拿一张纸，左边写“要保留的原始信息”，右边写“这些信息能藏在哪个位置”。矩阵置零就是一组经典范本，搞懂它，之后再看状态压缩、原地哈希、二维状态编码这类题都会顺手很多。不要只背答案，要把“为什么用第一行第一列当标记”这件事讲清楚，这才算真正过了这道题。