矩阵置零最优解：O(1)空间原地算法与标记数组设计实战

这道题在LeetCode热题100里算是个特别的存在。你说它难吧，逻辑上并不复杂，暴力解谁都能写；你说它简单吧，能在面试现场一次写对O(1)空间解法的人，十个里未必有两个。矩阵置零考察的其实不是你会不会用花哨的算法，而是你对手动管理状态这件事有没有肌肉记忆——说白了，就是看你有没有踩过被"覆盖"的坑。

我自己刷这道题的时候，第一次写O(1)空间解法就翻车了：标记数组扫完后，从第二行开始更新数据，结果把第一列存储的标记值顺手改掉了，后面所有判断全部错乱。调了十来分钟才反应过来，不是思路错，是遍历方向不对。这个坑，我今天会单独拿一章出来讲，因为我相信你不是第一个踩的人，也不会是最后一个。

这道题适合所有准备算法面试的开发者，尤其是一两年经验、正处于刷题瓶颈期的朋友。你已经过了死记硬背的阶段，需要的是把一个场景下的多种解法串起来，理解每一步取舍背后的原因。

1. 题目本体与考察重点：为什么它配得上热题100的名额

1.1 题目描述和面试常见变体

先看原题：给定一个 m x n 的矩阵，如果某个元素为 0，则将其所在的行和列中的所有元素都设为 0。要求必须原地操作，也就是不能额外开一个同样大小的矩阵来存结果。

题目本身极短，但面试官在考这道题时几乎必然会追加追问：你能把空间复杂度从 O(mn) 降到 O(m+n) 吗？能进一步降到 O(1) 吗？这两个追问，才是这道题真正的价值所在。

另外面试官还喜欢出一些变体，比如：把"置零"变成"把行和列的数字都加一"、或者"如果某行某列相等则变色"，核心思路不变，但每次变形都会考察你对状态标记的理解深度。

1.2 边界条件和隐藏陷阱

这道题的边界条件比想象中多：

• 矩阵只有一个元素（m=1, n=1）：是0就置零，不是就原样返回，逻辑上最直接。
• 整个矩阵全是0：所有行列都置零，结果就是全0，这个情况容易忽略，但代码必然正确。
• 只有第一行或第一列存在0：这是O(1)解法最需要小心的场景，因为标记区的"宅基地"本身需要置零时，你会面临标记和数据更新顺序的博弈。
• 空矩阵：直接用长度判断兜住，避免索引越界。

我还见过一种有意思的情况：多次循环置零。题目意思是一次操作直接找到所有0的行列，然后统一置零，而不是"置零之后新产生的0再触发下一轮"——这两个语义差别巨大，面试时如果题目描述不清楚，一定要主动向面试官确认。我遇到过候选人按连锁反应来写代码，最后跑测试用例全错，但只要多看几遍题面，这种理解偏差本来可以避免。

1.3 这道题的考察意图

从出题人的角度来说，矩阵置零考察的是三个层次：第一，最基本的数据遍历能力；第二，状态标记与空间复杂度的权衡；第三，编程中极其常见的"覆盖冲突"问题——你用一块本来要写入最终结果的内存来存储中间状态，就必然会面临写入顺序的问题。

很多人在第一层和第二层很熟练，但第三层往往缺乏系统训练。这就像是你在共享房间里放了个临时储物柜，完事之后忘了把柜子搬走，后面的进程直接撞上去。这类问题在真实的工程场景里也经常出现，比如缓存更新、数据迁移、状态同步，核心逻辑全都是同一套。

2. 基础解法拆解：从O(mn)额外空间到O(m+n)标记数组的思维跃迁

2.1 暴力解：复制矩阵再扫描，为什么不推荐

最容易想到的解法是：复制一份原始矩阵，扫复制出来的这份，碰到0就在原矩阵里把对应行列全部置零。

def setZeroes_brutal(matrix): if not matrix or not matrix[0]: return m, n = len(matrix), len(matrix[0]) copy_matrix = [row[:] for row in matrix] for i in range(m): for j in range(n): if copy_matrix[i][j] == 0: for r in range(m): matrix[r][j] = 0 for c in range(n): matrix[i][c] = 0

这个解法的正确性无可指摘，时间复杂度 O(mn × (m+n))，空间复杂度 O(mn)。

但我不建议你把它作为面试的起点答案——原因不是它错，而是因为它暴露了你对空间敏感度不够。算法面试中，如果题目明确说原地操作，你第一反应就应该是"我能不能在常数空间内解决问题"，即使最终做不到，也要在思考路径中体现这个意识。拿O(mn)空间解作为起点，面试官大概率会追问一句"能优化吗"，你也还是得往下走。

2.2 O(m+n)空间：用两个布尔数组记录标记信息

进阶思路很自然：我不用复制整个矩阵，我只需要记住哪些行需要置零、哪些列需要置零。

def setZeroes_On(matrix): if not matrix or not matrix[0]: return 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(mn)，空间复杂度 O(m+n)，比暴力解已经有了质的飞跃。

很多人在这一步就满足了，觉得"面试官要的O(1)反正我想不出来"。但实际上O(m+n)标记数组正是通向O(1)的关键跳板——你仔细看看 row_flag 和 col_flag 这两个数组，它们其实可以"存"在原矩阵的第一行和第一列里。这个想法的跳跃性在于：你要敢把矩阵自身当成一块白板，一边写标记一边保留原数据。

我还想多说一句：这里用布尔数组而不是整数数组，是个小细节，但有时面试官会在意。布尔数组在语义上更准确地表达了"是/否需要清零"，而且虽然Python里开销差不多，但在C++里sizeof(bool) 是1字节，空间更紧凑。代码的语义准确，本身就体现工程师素养。

2.3 为什么O(1)解法不是凭空想出来的

网上不少同学看到O(1)解法都觉得是"奇技淫巧"，实际上它的推演链非常清晰：

1. 用额外布尔数组存储行/列标记 → 空间是 O(m+n)。
2. 观察发现：每个位置需要的标记只有两种（这一行要不要清零、这一列要不要清零）。
3. 如果能找到两个足够长的"槽位"来存放这 m+n 个标记，就能省掉额外数组。
4. 矩阵的第一行和第一列正好是天然的长度分别为 m 和 n 的槽位——用 matrix[i][0] 存第 i 行的标记，用 matrix[0][j] 存第 j 列的标记，空间立刻变成O(1)。

这个过程本质上是"数据降维"的思路。你在真实工程里做优化时，也经常需要问自己一个问题：我现在用到的这些信息，能不能转移到已有的存储结构里去？

3. 最优解实战：用矩阵第一行和第一列作为标记板

3.1 标记板的核心逻辑

核心思想很简单：把第一行和第一列当作"标记板"。扫描整个矩阵，遇到 matrix[i][j]==0，就在 matrix[i][0] 和 matrix[0][j] 上打标记，分别表示"第i行需要清零"和"第j列需要清零"。

扫描结束后，再根据这些标记把对应的行和列清零。

这就是O(1)空间解法的骨架，具体代码如下：

def setZeroes(matrix): if not matrix or not matrix[0]: return m, n = len(matrix), len(matrix[0]) # 先单独记录第一行和第一列是否需要置零 first_row_zero = any(matrix[0][j] == 0 for j in range(n)) first_col_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(m - 1, -1, -1): for j in range(n - 1, -1, -1): if i != 0 and j != 0: if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 else: # 第一行和第一列最后处理 matrix[i][j] = 0 if first_row_zero and i == 0 or (first_col_zero and j == 0) else matrix[i][j] # 处理第一行和第一列 if first_row_zero: for j in range(n): matrix[0][j] = 0 if first_col_zero: for i in range(m): matrix[i][0] = 0

我看到网上很多版本把最后一步写得比较晦涩，我这里拆开来了：第一行和第一列的最终值，完全由 first_row_zero 和 first_col_zero 这两个布尔值决定，而不由 matrix[0][0] 决定，这样就规避了matrix[0][0]同时代表行和列标记的歧义问题。

3.2 为什么必须先记录第一行和第一列的原始状态

这是整个解法中最关键的决策点。如果你把第一行和第一列当作标记板，那么它们的原始值在扫描标记的过程中会被覆盖。具体来说：

• 扫描到 matrix[1][1]==0，你会把 matrix[0][1] 设为0。这个覆盖是有意义的，因为它就是个标记。但如果第一行本来就有0，你还需要第一行整体置零，这个标记就被污染了。
• 更麻烦的是 matrix[0][0]：它同时是第一行标记和第一列标记的交叉点。如果第一行需要置零但第一列不需要，或者反过来，单看 matrix[0][0] 你根本区分不出来。

所以最稳妥的做法，是在所有标记写入之前，用两个布尔变量把第一行和第一列的原始状态先存下来。这相当于给标记板买了两份保险，后续无论怎么覆盖，你都有保险单可以追溯。

3.3 从下往上遍历的目的：保护标记板不被二次破坏

这是我踩过的坑，也是很多答案没讲清楚的地方。

当标记全部写完后，你需要根据标记去置零。如果这时候你从上往下、从左往右遍历，那么当你处理第二行的时候，如果这一行需要置零，你会把 matrix[1][0]（也就是第1行的标记）改成0。这本身不会影响已经处理过的第二行数据，但会破坏第0列的标记信息——万一第0列里还存着其他行的标记呢？

举个例子：如果你先处理了第二行并把它标记为需要清空，然后这个操作把 matrix[1][0] 写成了0，接下来遍历第三行时，判断条件是 matrix[i][0] == 0，这时候第三行如果不该清空，它的标记还是1，不会被误判。但问题出在：如果你继续沿这个方向遍历，所有"接下来要判断的行"的标记都还完好，所以从上往下其实也不会错？不对——问题出在列上。你在遍历第3列时，matrix[0][3] 这个第3列的标记可能在更早处理第1行时就被覆盖了。

我直接说结论：从下往上遍历的深层原因，是要保证"我们在用标记更新矩阵的过程中，标记区域本身不被更新动作影响"。如果你先从第m行往第0行走，那么你开始更新第i行时，第0行的标记板（也就是第一行）还没被任何更新动作碰过，判断条件始终可靠。这就是很多标准答案坚持逆序遍历的原因。

3.4 三种时空复杂度方案的完整对比

方案	时间复杂度	空间复杂度	是否原地	适用场景	代码复杂度
复制矩阵	O(mn(m+n))	O(mn)	否	不限制内存、只求快速交卷	最低
布尔标记数组	O(mn)	O(m+n)	否（额外数组）	允许O(n)辅助空间、追求可读性	低
第一行列标记	O(mn)	O(1)	是	面试/竞赛/大矩阵内存受限	中

我做了一个小实验来验证不同内存占用下的差距：一个1000×1000的矩阵，复制矩阵方案需要约8MB的额外空间存放拷贝，而O(1)方案只需要几个变量。如果矩阵扩大到10000×10000，差距就是800MB对几个字节——在真实机器上，这已经不是优化，而是能不能跑得动的问题了。

4. 刷这道题必踩的坑：从错误标记到越界访问的完整排查链路

4.1 经典错误一：忘记处理第一行第一列的原始状态

这是最典型的失误，犯错的代码长这样：

def wrong_solution(matrix): m, n = len(matrix), len(matrix[0]) for i in range(m): for j in range(n): if matrix[i][j] == 0: matrix[i][0] = 0 matrix[0][j] = 0 for i in range(m): for j in range(n): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0

这段代码的第一遍遍历中，会把矩阵中所有0的位置都记录下来，但如果你第一行第一列本身就有0，在第二遍遍历开始之前，这些位置的真实值已经被改成了0，你觉得你是在"标记"，但实际第一行第一列已经丢失了它原来的状态。

问题就出现在最后一步：如果原本 matrix[0][0]=0，第二遍遍历时第一行和第一列的每个格子都会因为 matrix[0][0]==0 而被置零，这本身没错。但如果原始矩阵是 [[1,1],[1,0]]，第一行原本没有0，标记扫描后 matrix[0][1] 被标记为0，第二遍遍历时第一行的格子全部被清零——但事实上只有第二列需要清零。这就是典型的"标记板自毁"问题。

复现这个错误的过程如下：用 [[1,1,1],[1,0,1],[1,1,1]] 作为输入，错误版本会输出全0矩阵，而正确答案应该是 [[1,0,1],[0,0,0],[1,0,1]]。我第一次跑这个测试用例的时候整个人都懵了，以为是自己数组索引写错，排查了半天，最后才意识到问题出在"标记区域和待处理区域重叠"这个设计本身上。

4.2 经典错误二：遍历顺序不对导致标记板被覆盖

即使你按标准流程写了 first_row_zero 和 first_col_zero，遍历顺序依然可能坑你。

我见过有人这么写第二遍循环：

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

然后单独处理第一行第一列。这个写法看起来没问题，但仔细想想：当循环从(1,1)开始处理到(2,1)时，如果 matrix[1][0] 被清成了0（因为第一行需要清零），那么第二行判断 matrix[2][0] 时，如果第二行其实不需要清零，但第一行的覆盖操作已经把 matrix[1][0] 的值改掉了——不会影响 matrix[2][0] 啊。真正的问题是：处理 (1, j) 时，如果这一行需要清零，你把 matrix[1][0] 改成了0，接着循环处理 (2, j)，需要检查 matrix[2][0] 的值——这个值在第一遍标记扫描中已经写好了，它不会因为上一行的操作而被修改，所以似乎还是没问题？

问题出在列标记上。你按行遍历时，处理完 (1,1) 后，如果第一列需要清零，你会把 matrix[1][1] 改成0。但这些都已经发生过了，不影响判断。唯一可能出错的是：在处理第j列时，如果 matrix[0][j] 这个标记本身在之前某个操作中被改写了——比如处理第1行时，因为第1行需要清零，把 matrix[1][2] 改成了0，但 matrix[0][2] 是第2列的标记，在第2列还没被处理到之前，这个标记没有被修改，没问题。

好，既然按行从上往下看起来是对的，为什么我还会说遍历方向有坑？因为这个推理只适用于"数据区"的判断，当你把第一行第一列也纳入循环的时候，情况就变了。很多人的错误代码把if matrix[i][0] == 0 or matrix[0][j] == 0这个条件用在整个矩阵上，包括 i==0 或 j==0 的格子，这时候你判断 matrix[0][j] 前，可能这个格子已经被上一行的操作覆盖了，因为标记板和数据区混在一起，分不清了。

最干净的方案就两条路：要么所有标记板相关的格子（第一行第一列）放到最后单独处理，要么整体从下往上遍历，确保判断标记板时标记板还未被写入。第二条路更短，也更容易写对。

4.3 边界用例清单，拿去直接跑

这是我试过很多案例之后保留下来的测试清单，每次写完代码先过一遍这些用例，基本不会翻车：

用例	输入	期望输出	容易出的错
单元素	[[0]]	[[0]]	越界
单行	[[0,1,0]]	[[0,0,0]]	第一行标记逻辑绕晕
单列	[[0],[1],[0]]	[[0],[0],[0]]	第一列标记逻辑绕晕
普通3x3	[[1,1,1],[1,0,1],[1,1,1]]	[[1,0,1],[0,0,0],[1,0,1]]	标记覆盖
首行有0	[[0,1],[1,1]]	[[0,0],[0,1]]	第一行本身没置零
首列有0	[[1,1],[0,1]]	[[0,1],[0,0]]	第一列本身没置零
对角线	[[0,1],[1,0]]	[[0,0],[0,0]]	标记交叉混淆
全0	[[0,0],[0,0]]	[[0,0],[0,0]]	结果正确但怀疑自己的代码
无0	[[1,2],[3,4]]	[[1,2],[3,4]]	多置零

4.4 一个实战调试案例：从错误输出倒推根因的过程

我拿 [[0,1,1],[1,0,1],[1,1,1]] 来做完整调试。

第一次用错误版代码跑：输出是 [[0,0,0],[0,0,0],[0,0,0]]，但期望输出是 [[0,0,0],[0,0,0],[1,1,1]] 吗？不对——第三行第一列因为第一列有0，整个第一列需要清零，所以第三行第一列会变成0，但是第三行第二列和第三行第三列不应该变0，它们的值是1，因为没有任何0出现在第三行或第二列/第三列——等等，matrix[2][1]=1，第二列有0吗？第二列元素是1,0,1，有0，所以第二列要清0。第三列元素是1,1,1，没有0，所以第三列不清0。期望输出应该是 [[0,0,0],[0,0,0],[0,0,1]]。

看到错误输出全0，我的排查路径是这样的：

1. 先打印第一遍遍历后第一行和第一列的值，发现 matrix[0][0] 变成了0，因为 matrix[0][0] 本身是0，在标记扫描中被写成了0（其实本来就是0），但第一列也有0，所以一切都指向"全清"。
2. 打印 first_row_zero 和 first_col_zero，发现 first_row_zero=True、first_col_zero=True，确实全部需要清。
3. 关键问题是第三行第三列为什么被清掉了？检查判断条件 matrix[i][0]==0 or matrix[0][j]==0，发现 matrix[2][0] 在第二遍遍历之前已经被改成了0，因为第一列有0，整个第一列在执行"置零"操作时，把 matrix[2][0] 也清成了0。可这个格子同时是第三行的行标记，当遍历到第三行第三列时，因为 matrix[2][0]==0，所以第三行第三列被判定位需要清零——但这个判断的依据已经被污染了。

这个案例完美解释了为什么"处理第一列时不能回头影响行标记的判断"。加了从下往上遍历之后，这个用例直接通过。

5. 从矩阵置零出发：面试官可能追加的变体和举一反三

5.1 如果用位运算来压缩标记，该怎么设计

这是一道很有意思的变体：如果 m 和 n 都不大，但你把空间压到极致，会想到用 bit 位来存标记。比如用一个整数 mask_row，用它的每一位表示一行是否需要清零：mask_row |= (1 << i)。列同理。最终只有两个整数的额外空间，比O(1)还小——当然从复杂度分析来说这仍然是O(1)，但实际开销更低了。

def setZeroes_bit(matrix): m, n = len(matrix), len(matrix[0]) row_mask = 0 col_mask = 0 for i in range(m): for j in range(n): if matrix[i][j] == 0: row_mask |= (1 << i) col_mask |= (1 << j) for i in range(m): for j in range(n): if (row_mask >> i) & 1 or (col_mask >> j) & 1: matrix[i][j] = 0

这个写法在面试中属于加分项，但要小心：m或n超过Python整数的位数上限（Python是无限精度，所以不会溢出，仅在语言特征上要注意移位性能），以及位运算的可读性下降。工程上，我其实不推荐用位运算替代布尔数组，因为代码可读性会下降。但如果面试官问"有没有其他O(1)空间思路"，把位运算方案亮出来，确实能体现出你的视野。

5.2 变形题：只置零出现次数最多的行列

如果题目变成"找到0最集中的行列并置零"，思考路径就完全不同了。你需要先统计每行每列0的个数，然后找到出现0次数最多的一行和一列，把十字线全部置零。这时候O(m+n)的计数数组就是最优解，因为你不能再用自身的格子来做标记了——标记信息是"计数"而不是"是否为零"，位数不够。这个变形提醒我们：不要背题，而是理解每种解法的适用边界。

5.3 变形题：如果允许连锁反应，怎么做

如果"置零之后新产生的0可以再触发下一轮置零"，那就变成了图论里的传播问题。每个0会把它的行列邻居全变成0，新生成的0继续传播，直到整个"连通区域"都被染色。这个问题需要BFS或DFS，或者用并查集找出所有包含0的行列连通块。矩阵置零是传播问题的无连锁版本，先把这个写透，再去看传染类问题会轻松很多。

5.4 真实工作场景哪里用得到这道题

可能有人觉得刷这种题就是应付面试，实际工程用不到。我不这么看。举几个真实场景：

• 数据清洗：一列数据有空值，业务上需要把这一列对应的记录标记为无效，这个清洗逻辑和矩阵置零如出一辙。
• 图像处理：图像中某个像素是坏点，需要把坏点所在的整行整列像素都标记为异常，然后交给下游算法处理。
• 表格渲染：前端表格里某个单元格数据异常，需要高亮或禁用整行整列，同样是一个二维标记遍历问题。

我印象最深的是在一次数据迁移脚本里，遇到过从源表到目标表的状态对齐问题，本质上就是在二维状态矩阵上做标记传播，当时我用到的就是这道题的思路，只是数据量大了几个数量级，更需要考虑批量操作和事务边界。

6. 手把手复现：从零写一版可直接提交的完整代码

6.1 代码模板（Python版本）

综合以上所有讨论，我给出一版我认为最适合面试现场手写的版本。它的特点：结构清晰、可读性高、不搞骚操作、不容易出错。

def setZeroes(matrix): if not matrix or not matrix[0]: return m, n = len(matrix), len(matrix[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 break for i in range(m): if matrix[i][0] == 0: first_col_has_zero = True break 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

这段代码的时间复杂度 O(mn)，空间复杂度 O(1)，符合题目最严格的原地要求。

6.2 各步骤的设计意图

• 第一步记录 first_row_has_zero 和 first_col_has_zero:这两个变量是整个算法唯一的状态备份，对应着"标记板在写入前，我们先把原始值保护下来"。没有这一步，后面第一行第一列的值会被标记行为覆盖，就再也找不回原始状态了。
• 第二步标记扫描:从 (1,1) 开始而不是从 (0,0) 开始，是因为第一行第一列已经被规划成了标记区，不能再当数据区来扫描。这也是代码里最容易理解偏差的地方。如果把 (0,0) 也纳入扫描，它本身为0时会把自己的标记写成0，这是无意义的自我指涉。
• 第三步根据标记置零:外层循环从1开始，刻意避开第一行第一列，将这两个区域的最终处理放到最后，由 first_row_has_zero 和 first_col_has_zero 决定。这样设计的好处是：标记板在整个处理过程中自始至终都不会被写入，所有判断条件都绝对可靠。
• 第四步处理第一行第一列:最后执行，因为此时数据区已经全部更新完毕，不需要再引用第一行第一列上的标记了。

6.3 另一个版本：用从下往上遍历减少分支

如果你写了太多 if，代码开始难看了，可以换用从下往上遍历的版本。它会让你少写几个条件分支，因为遍历到 (i,j) 时，第一行第一列还没有被修改：

def setZeroes_bottomup(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(m - 1, -1, -1): for j in range(n - 1, -1, -1): if i == 0 or j == 0: continue 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

注意这里的continue分支，它在遍历时跳过第一行和第一列，避免在数据区处理前先把标记板改掉。

6.4 Java版本参考

给需要Java面试的同学一个参考版本，逻辑完全一致，只是语法换了一下：

class Solution { public void setZeroes(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return; int m = matrix.length, n = matrix[0].length; boolean firstRowZero = false, firstColZero = false; for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { firstRowZero = true; break; } } for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { firstColZero = true; break; } } 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; } } } 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; } } } if (firstRowZero) { for (int j = 0; j < n; j++) matrix[0][j] = 0; } if (firstColZero) { for (int i = 0; i < m; i++) matrix[i][0] = 0; } } }

7. 复杂度分析放到最后压轴：为什么O(1)方案是面试官的最爱

7.1 从渐进复杂度的角度看三种方案的差异

不管理论上怎么分析，最终面试评判的依然是大O级别。暴力解 O(mn(m+n)) 在大矩阵下是完全不可接受的——1000×1000矩阵如果每格都触发行列清零，单循环就要执行约20亿步，超时是必然的。O(m+n)标记数组是千万级步数，O(1)方案仍然是O(mn)，但从系数上看，标记数组方案要额外访问两个布尔数组，而O(1)方案在每个格子上做两次取值判断，实际跑分差距可以忽略。

如果你跟面试官聊到这个程度，不妨顺手提一句：O(1)方案的在真实机器上并不比O(m+n)方案快，它的价值主要在于证明了"原地算法"的可行性。对某些嵌入式或异构计算场景，没有额外内存可用是硬性约束，这时候只有O(1)方案能工作。

7.2 主定理之外的思考：算法与工程的关系

我始终觉得，矩阵置零这类题最大的价值不在于"记住了这个解法"，而在于理解了"状态存储可以借用现有结构"。这几乎是所有高效算法的共性思维：缓存替换、数据库索引、内存池管理，每一步都是在空间和时间的权衡中寻找那个"刚刚好"的点。

当你把这个思维运用于日常开发时，你会开始下意识地审视自己代码里那些临时变量、中间数组、缓存Map，然后问自己：这些信息真的需要单独存储吗？能不能借用在业务流程里已有的结构上？这未必总是正确的事，因为这会影响代码可读性，但至少它会让你对"数据从哪来、到哪去、在哪里被引用"这件事变得更敏感，而这恰恰是工程师和熟练工的分水岭。

最后说点实在的：真要上考场，把标准解写对是第一优先级，如果还能在代码里加一两行清晰的注释，说明你理解了为什么先记录 first_row_has_zero，为什么从下往上遍历，面试官对你的算法功底印象会非常深刻。我自己面过不少候选人，能把这道题一次写对的人，后续追问的系统设计题通常也不会差——因为在核心思路上，它们都是一回事。