企业官网建设流程全解析

刷算法题的人应该都听过一句话：面试考的不是你会不会做，而是你会不会在限制条件下做。LeetCode 73矩阵置零就是典型代表。这道题看着简单——遍历矩阵找0，再把对应行列全部置零，但真正动手写起来，大多数人的第一版解法都会在空间复杂度上栽跟头。今天这篇就把这道题从暴力到原地算法的完整思路、边界条件和实战细节展开聊透，尤其是原地算法那几步为什么要按特定顺序执行，我会把每一步背后的逻辑讲明白。

写这篇文章的读者画像很清晰：准备算法面试、刷LeetCode热门100题的人，或者工作中需要处理二维数组操作、被空间限制卡过的人。就算你刚接触矩阵类题目，只要按着文章的节奏走，也能把这道题从“会做”提升到“能讲清楚”的水平。关键点只有一个：理解为什么“用矩阵自身记录标记”是可行的，以及第一行第一列那套标记法为什么能成为标准答案。

1. 这道题真正的坎：不是找零，而是保存现场

1.1 直接修改为什么会让矩阵“全盘崩坏”

先看一个最简单的例子。假设输入是：

[[1, 1, 1], [1, 0, 1], [1, 1, 1]]

很多人第一反应是：遍历，遇到matrix[1][1] == 0，就把第1行和第1列全部置零。输出确实对了：

[[1, 0, 1], [0, 0, 0], [1, 0, 1]]

但换个例子试试：

[[0, 1, 1], [1, 1, 1], [1, 1, 1]]

如果沿着(0,0)这个0把第0行和第0列全部置零，矩阵变成：

[[0, 0, 0], [0, 1, 1], [0, 1, 1]]

接着遍历到(1,1)时，它本来不是0，但如果你此刻再次扫描整个矩阵，会把第1行和第1列也置零，最终整个矩阵全是0。错得离谱。

问题出在哪？出在“遍历”和“修改”混在了一起。你一边在判断哪些位置需要处理，一边又在改矩阵，改出来的新0又被当成原始信息继续扩散。这就像一个厨师一边看菜谱一边改菜谱，最后做出来的菜连他自己都不知道是什么。

所以这道题的第一条铁律是：判断依据必须和修改操作分离。你要么先把所有0的位置记录下来，再统一修改；要么用一块不会被修改操作污染的区域来保存标记。所有后续优化，都是围绕这第一条铁律展开的。

1.2 空间约束是出题人给的路线图

题目里有一句很容易被忽略的要求：“原地算法”，也就是空间复杂度O(1)。这句话直接堵死了最省事的方案——拷贝一个同样大小的矩阵，在新矩阵上操作，再把结果搬回去。虽然很多人第一反应就是这个，但面试官考的就是你能不能绕过这个“直觉陷阱”。

这里要厘清一个概念：原地算法也不意味着完全不能用额外空间，只是额外空间必须跟m和n无关，也就是O(1)。你可以用几个临时变量、几个布尔值，但你不能用长度和矩阵维度成正比的数组、集合、哈希表。

理解了这条约束，解题思路其实就清晰了：既然不能用外部数组记录哪些行哪些列有0，那就只能在矩阵自己身上想办法。矩阵身上有哪些地方是“不用白不用”的？第一行和第一列。这就是原地算法最核心的出发点。

2. 先写出O(m+n)版本：标记数组是理解原地算法的跳板

2.1 标记数组实现：发现与修改分离

在跳到原地算法之前，先写出O(m+n)空间版本很有必要。它不仅是正确性最容易保证的方案，也是面试时解释思路的好起点。

def setZeroes(matrix): m, n = len(matrix), len(matrix[0]) row = [False] * m col = [False] * n for i in range(m): for j in range(n): if matrix[i][j] == 0: row[i] = True col[j] = True for i in range(m): for j in range(n): if row[i] or col[j]: matrix[i][j] = 0

逻辑很直白：第一遍遍历只负责“记录”哪些行、哪些列有0，第二遍遍历再根据记录把对应位置改成0。因为第一遍没有修改矩阵内容，所以信息不会丢失。

这个版本的空间复杂度是O(m+n)，即两个一维数组。这里的row[i] = True表示“第i行需要全部置零”，col[j] = True表示“第j列需要全部置零”。第二遍遍历时，只要位置(i, j)所在的行或列有标记，就置0。这个条件判断是同时判断行列，不会重复处理，也不会漏处理。

2.2 从复杂度到面试追问：空间还能不能省

面试官看到这个版本通常会点头，然后立刻追问：“能不能把空间降到O(1)？”这就是在逼你思考：row和col这两个数组的信息，能不能换个地方存？

要回答这个问题，先想想row和col数组的本质是什么：它们分别是长度为m和n的布尔数组，记录的事实是“哪些行有0”和“哪些列有0”。而矩阵自身的第一列是不是刚好有m个位置？第一行是不是刚好有n个位置？如果拿第一列来替代row数组、拿第一行来替代col数组，信息量完全对得上。

这就是原地算法的关键转折点：用矩阵自己的第一行和第一列作为标记区。一旦想到这一步，剩下的就是处理“标记区自身被污染”的问题。

3. 原地标记：把第一行第一列当成随身便签

3.1 为什么第一行第一列是天然的标记面板

想象你有一块白板，要记录房间里哪些人举了手。白板本身可能也有字，但那是旧信息。现在你的任务是把“谁举手”记在白板上，最后再把白板擦干净重新写。矩阵的第一行第一列就是这块白板。

具体来说：

• 用matrix[i][0]（第i行第一个元素）来表示“第i行是否含0”
• 用matrix[0][j]（第j列第一个元素）来表示“第j列是否含0”

第一遍扫描剩余区域时，如果发现matrix[i][j] == 0，就在matrix[i][0]和matrix[0][j]处打上0标记。这个过程叫做“标记回写”。

但是这里有个问题：如果第一行本身就有0，那matrix[0][j]就被污染了；如果第一列本身就有0，那matrix[i][0]也被污染了。更麻烦的是，标记区自身的信息也会被当成标记，产生连锁反应。所以必须先保存第一行和第一列各自的原始状态。

3.2 两个额外变量在解决什么问题

这就是两个额外布尔变量的来源：first_row_has_zero和first_col_has_zero。

first_row_has_zero = any(x == 0 for x in matrix[0]) first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))

这两个变量在开头就把第一行、第一列的“原始信息”抽离出来保存。为什么要保存？因为后面第一行第一列会被当作标记区使用，原值会被改掉，如果不提前记录，到最后一步就不知道第一行、第一列本身是否该被置零。

这里有一个常见的理解误区：有同学问，既然第一行第一列要拿来当标记区，那它们自己的值不重要了吗？不是不重要，而是“先把原始信息存到变量里，再让它们去当标记区”。最后一步还要用保存的变量把第一行第一列恢复成正确结果。变量只占O(1)空间，不违反原地算法的约束。

3.3 原地算法的四步主流程

完整流程可以拆成四步：

第一步，先遍历第一行和第一列，记录它们是否含0，分别存入两个布尔变量。

第二步，从(1,1)开始遍历剩余矩阵。如果遇到matrix[i][j] == 0，就把matrix[i][0]和matrix[0][j]改为0。注意，这一步是从(1,1)开始的，绝不能从(0,0)开始。因为第一行第一列是标记区，你一边标记它一边判断它，会把“标记值”当成“原始值”，导致错误扩散。

第三步，再次从(1,1)开始遍历剩余矩阵。如果matrix[i][0] == 0或matrix[0][j] == 0，就把matrix[i][j]置为0。这一步是根据标记区里的信息，把真正需要置零的行列元素都改掉。

第四步，根据第一步保存的两个布尔变量，处理第一行和第一列。如果first_row_has_zero为真，把第一行全部置0；如果first_col_has_zero为真，把第一列全部置0。

这个顺序必须严格遵守，尤其第三步和第四步不能交换。如果先把第一行第一列处理了，后面再根据标记区处理其他区域时，标记区已经被改掉，后面的判断就会失真。

4. 细节才是分水岭：边界条件与处理顺序

4.1 单行、单列、全零矩阵的边界表现

很多人在LeetCode上提交原地版本后，会在特殊用例上翻车。最常见的三个边界场景是：单行矩阵、单列矩阵、全零矩阵。

单行矩阵，比如[[1, 0, 1]]。第一步遍历第一行时，first_row_has_zero检测到0，为True。然后第二步从(1,1)开始，但m = 1，根本不会进入循环，不会产生任何标记。第三步也不会进入。第四步根据first_row_has_zero把第一行全部置零，得到[[0, 0, 0]]，正确。

单列矩阵，比如[[1], [0], [1]]。第一步first_col_has_zero为True，第二步循环j从1到n-1，但n = 1，循环不执行，不会产生标记。第三步同理。第四步把第一列全部置零，得到[[0], [0], [0]]，正确。

全零矩阵则更简单，所有步骤都正常执行，标记区本身就是0，最后结果还是全0，不会出错。

这些边界情况想明白了，就知道为什么两个布尔变量是必需的：在单行或单列场景下，标记区完全没有被使用的机会，只能靠变量兜底。

4.2 为什么必须从矩阵右下角方向处理

有些题解里，第三步处理时会从右下角往左上角倒着遍历，而不是从(1,1)开始顺着遍历。这涉及到一个容易被忽略的问题：正序遍历时，会不会把刚置成的0又当成标记继续扩散？

答案是：如果你严格只在第三步用“标记区”来判断，也就是只判断matrix[i][0]和matrix[0][j]，那么正序和倒序都能得到正确结果。因为你判断依据只来自标记区，不会读取matrix[i][j]自身的值。但如果某个版本的写法在第三步同时依赖matrix[i][j] == 0进行判断，正序遍历就会出问题。

不过倒序有一个额外优势：如果最后一步要处理第一行第一列，倒序遍历可以保证第一行第一列的标记在全部使用完之后再被覆盖。以我个人的习惯，我更喜欢用一个额外变量版本时采用倒序，两变量版本时正序倒序都行，选顺手就好。

4.3 单变量版本的双刃剑写法

网上还有一种优化写法，只用一个额外变量，核心思想是：用matrix[0][0]这个位置本身来记录“第一行是否含0”，再用一个变量col0记录“第一列是否含0”。代码长这样：

def setZeroes(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[0][0]承担了双重身份：既是第一行是否有0的标记，又是第一列是否有0的标记（当i=0时matrix[0][0]会被写）。你必须很熟悉每一步的执行顺序，才能在面试的高压环境下不出错。我不太推荐面试时写这个版本，除非你私下练得滚瓜烂熟。两个布尔变量的版本逻辑更清晰，跟面试官解释时也更好懂。

5. 实测观察：时空开销和面试展示策略

5.1 三种方案的空间占用对比

把三种实现放到LeetCode上实际跑，结果很有意思。暴力拷贝版本和标记数组版本在内存上的差异很明显，而原地算法相比标记数组版本，内存又有进一步下降。

LeetCode评测数据不一定能把三者拉开肉眼可见的差距，尤其在小矩阵上，内存差异只有几KB。但在面试沟通中，空间复杂度的理论分析远比评测数据重要。

5.2 时间复杂度几乎相同的背后

三类方案的时间复杂度都是O(mn)，但只要跑过测试就会发现，实际耗时并不完全一样。原地算法要遍历矩阵三次：第一次遍历剩余区域打标记，第二次根据标记置零，第三次处理第一行第一列，外加之前第一行第一列的两次扫描。标记数组方案只需要遍历两遍。这个差异属于常数倍的差异，不影响复杂度的量级。

所以这道题的时间优化空间不大，真正的技术含量在于“如何在省空间的条件下保持正确的信息流”。这也是为什么面试官不会揪着耗时细说，而是更看重你对空间约束的理解。

5.3 面试时我建议的答题顺序

实战经验告诉我，面试时最稳的节奏是：

第一步，先说出最直观的暴力解，解释它为什么不满足原地要求。这展示了你的基础认知。

第二步，说出标记数组版本，写出代码，分析复杂度O(m+n)。

第三步，在面试官追问后，说出原地版本。这时候重点不是直接甩代码，而是先讲思路：“用第一行和第一列当作标记面板，再用两个布尔变量保存面板本身的原始状态。”然后写出两变量版本，并且逐行解释。

第四步，主动说出边界条件，比如单行矩阵、第一行含0等，并说明两个布尔变量怎么兜底。

这套顺序能展现你的思考过程是递进的，不是背答案。很多刷题的人直接把最优解甩出来，面试官反而看不出你经历了什么思考。

6. 排雷现场：那些很容易翻车的实现

6.1 边遍历边置零的错误示范与分析

我在刷题群里见过不下十次这种写法：

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

这种写法用2x2小矩阵测的时候可能碰巧对了，但一旦矩阵里的0不止一个，或者0不在对角线位置，立刻出错。原因前面已经分析过：新生成的0会继续触发置零逻辑。现在还多了一个问题：当i遍历到后续行时，可能碰到已经被置成0的matrix[i][j]，又触发一次行列置零，最后整个矩阵全灭。

这里要记住一个判断技巧：如果某个位置的0可能不是原始0，那它就不能作为触发条件。凡是需要在修改过程中做判断的，必须确保判断来源是“原始数据”或“可靠的标记区”。

6.2 用Set存位置虽然能过但并非最优

还有一种思路是用两个set分别存有0的行和列：

zero_rows = set() zero_cols = set() for i in range(m): for j in range(n): if matrix[i][j] == 0: zero_rows.add(i) zero_cols.add(j)

这个思路和标记数组本质上一样，空间占用最坏情况下会达到O(m+n)，因为当每一行每一列都有0时，set里会存满所有行号和列号。虽然写起来比数组顺手，而且能通过LeetCode的全部用例，但严格来讲它不满足O(1)空间的限制。面试时如果只写这个版本，大概率会被追问。

6.3 手造边界样例的检查清单

我每次写完原地算法，都会用下面这些样例自查一遍，这已经成了肌肉记忆：

1. [[1,1,1],[1,0,1],[1,1,1]]：最普通的场景，验证基本逻辑。
2. [[0,1,1],[1,1,1],[1,1,1]]：第一行第一列交叉位置有0，验证两个布尔变量是否生效。
3. [[1,1,1],[1,1,1],[1,1,0]]：右下角有0，验证标记回写是否把最后一行最后一列正确置零。
4. [[1,0,1]]：单行矩阵，验证first_row_has_zero兜底。
5. [[1],[0],[1]]：单列矩阵，验证first_col_has_zero兜底。
6. [[1,1],[1,1]]：没有任何0，确定矩阵保持不变。
7. [[0]]：单个元素正好是0的极端情况。

这七个样例涵盖了大多数边界情况。如果你手写代码后能一次性通过这些用例，提交基本不会出问题。

最后再说一个个人习惯：这道题我最开始也是直接背题解，后来发现一旦把“为什么标记区必须避开第一行第一列自身”想通，整个代码就再也不容易写错了。刷题的时候遇到这种空间受限的题目，不妨都像这样想一想：那些不让用的额外空间，能不能换成矩阵里“暂时不重要的位置”？这个思路迁移到其他题目里，比如判断数独、螺旋矩阵、矩阵旋转，其实都通用。