刷算法题的人应该都听过一句话面试考的不是你会不会做而是你会不会在限制条件下做。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(mn)版本标记数组是理解原地算法的跳板2.1 标记数组实现发现与修改分离在跳到原地算法之前先写出O(mn)空间版本很有必要。它不仅是正确性最容易保证的方案也是面试时解释思路的好起点。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(mn)即两个一维数组。这里的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的标记当i0时matrix[0][0]会被写。你必须很熟悉每一步的执行顺序才能在面试的高压环境下不出错。我不太推荐面试时写这个版本除非你私下练得滚瓜烂熟。两个布尔变量的版本逻辑更清晰跟面试官解释时也更好懂。5. 实测观察时空开销和面试展示策略5.1 三种方案的空间占用对比把三种实现放到LeetCode上实际跑结果很有意思。暴力拷贝版本和标记数组版本在内存上的差异很明显而原地算法相比标记数组版本内存又有进一步下降。方案额外空间时间复杂度实测内存表现m,n较大时拷贝矩阵O(mn)O(mn)极高大矩阵直接MLE风险标记数组O(mn)O(mn)中等mn变大时同步上升原地算法两变量O(1)O(mn)稳定不随输入规模变化LeetCode评测数据不一定能把三者拉开肉眼可见的差距尤其在小矩阵上内存差异只有几KB。但在面试沟通中空间复杂度的理论分析远比评测数据重要。5.2 时间复杂度几乎相同的背后三类方案的时间复杂度都是O(mn)但只要跑过测试就会发现实际耗时并不完全一样。原地算法要遍历矩阵三次第一次遍历剩余区域打标记第二次根据标记置零第三次处理第一行第一列外加之前第一行第一列的两次扫描。标记数组方案只需要遍历两遍。这个差异属于常数倍的差异不影响复杂度的量级。所以这道题的时间优化空间不大真正的技术含量在于“如何在省空间的条件下保持正确的信息流”。这也是为什么面试官不会揪着耗时细说而是更看重你对空间约束的理解。5.3 面试时我建议的答题顺序实战经验告诉我面试时最稳的节奏是第一步先说出最直观的暴力解解释它为什么不满足原地要求。这展示了你的基础认知。第二步说出标记数组版本写出代码分析复杂度O(mn)。第三步在面试官追问后说出原地版本。这时候重点不是直接甩代码而是先讲思路“用第一行和第一列当作标记面板再用两个布尔变量保存面板本身的原始状态。”然后写出两变量版本并且逐行解释。第四步主动说出边界条件比如单行矩阵、第一行含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(mn)因为当每一行每一列都有0时set里会存满所有行号和列号。虽然写起来比数组顺手而且能通过LeetCode的全部用例但严格来讲它不满足O(1)空间的限制。面试时如果只写这个版本大概率会被追问。6.3 手造边界样例的检查清单我每次写完原地算法都会用下面这些样例自查一遍这已经成了肌肉记忆[[1,1,1],[1,0,1],[1,1,1]]最普通的场景验证基本逻辑。[[0,1,1],[1,1,1],[1,1,1]]第一行第一列交叉位置有0验证两个布尔变量是否生效。[[1,1,1],[1,1,1],[1,1,0]]右下角有0验证标记回写是否把最后一行最后一列正确置零。[[1,0,1]]单行矩阵验证first_row_has_zero兜底。[[1],[0],[1]]单列矩阵验证first_col_has_zero兜底。[[1,1],[1,1]]没有任何0确定矩阵保持不变。[[0]]单个元素正好是0的极端情况。这七个样例涵盖了大多数边界情况。如果你手写代码后能一次性通过这些用例提交基本不会出问题。最后再说一个个人习惯这道题我最开始也是直接背题解后来发现一旦把“为什么标记区必须避开第一行第一列自身”想通整个代码就再也不容易写错了。刷题的时候遇到这种空间受限的题目不妨都像这样想一想那些不让用的额外空间能不能换成矩阵里“暂时不重要的位置”这个思路迁移到其他题目里比如判断数独、螺旋矩阵、矩阵旋转其实都通用。