 到 O(1) 的原地算法优化)
最近有朋友在准备算法面试刷到 LeetCode 73 题矩阵置零时卡住了。这道题我前前后后做过三遍第一遍用额外矩阵复制第二遍用两个集合标记第三遍才真正把原地方案吃透。今天把整个思考链路完整梳理一遍包括三种解法的演进、O(1)空间实现为什么能成立以及我实际写代码时踩过的坑。先交代一下题目本身给定一个 m×n 的矩阵如果某个元素是 0就把这个元素所在的整行和整列都置为 0。注意不是只改当前位置而是所有 0 都要扩散成整行整列。题目要求不要用额外的大空间来完成最优解是原地处理。这道题在算法面试里出现频率很高考察点非常集中一是你是否清楚“检测”和“修改”必须分离二是你能不能把空间复杂度从 O(mn) 逐步压缩到 O(1)。下面我从题目本质开始拆。1. 题目到底在考什么1.1 先读懂题目标记与执行必须分离先看一个最简单的例子。假设矩阵是1 2 3 4 0 6 7 8 9输出应该是1 0 3 0 0 0 7 0 9原因很简单元素 0 在第 1 行第 1 列下标从 0 开始所以第 1 行全部变 0第 1 列也全部变 0。矩阵里其他位置保持原样。这个例子只涉及单个 0看不出难度。真正的坑出现在多个 0 叠加的场景。比如0 2 3 4 0 6 7 8 9第一个 0 在 (0,0)第二个 0 在 (1,1)。(0,0) 会导致第 0 行和第 0 列清零(1,1) 会导致第 1 行和第 1 列清零。两者叠加之后整个矩阵几乎全部变 0。这里就引出了全题最关键的一个原则置零是一次性的扩散不是涟漪式的连锁反应。某个位置因为“行里有 0”或者“列里有 0”而变成 0 之后这个新产生的 0 不应该再继续去引发它自己所在行和列的二次清零。用一个生活类比来说这就像广播通知你得先收集完所有需要通知的人员名单然后统一广播。如果在广播过程中不断把新听到消息的人继续加入名单、继续广播消息就会越传越多最终失去控制。所以正确思路一定是先扫描记录所有需要被清零的行和列再统一执行清零。检测阶段和执行阶段必须分开这是整道题的地基。1.2 空间复杂度是真正的考点这道题的时间复杂度几乎没有讨论空间因为不管用什么方法你都得把矩阵里的每个格子至少看一遍所以时间必然是 O(mn)。真正的区分度在空间复杂度面试官几乎必然会沿着下面这条线引导你第一档空间 O(mn)复制一份矩阵当“判决依据”。代码简单但空间开销大。第二档空间 O(mn)只记录有 0 的行和列。这一步已经足够日常工程使用。第三档空间 O(1)把标记信息直接存回矩阵自己的第一行和第一列。这也是这道题最有魅力的一步。面试官通常不指望你上来就写 O(1) 版本而是看你能不能从最容易想到的方案开始一层一层优化下去并且解释清楚每一步为什么正确。很多人能写出前两种但到 O(1) 那一步就开始乱了原因就是对“标记与执行必须分离”这个底层逻辑理解得不够透。2. 解法演进从“会做”到“最优解”2.1 解法一复制矩阵最直观但不推荐最容易想到的方案是复制一份矩阵然后遍历原矩阵。只要原矩阵某个位置是 0就把复制矩阵的对应整行整列全部改成 0。最后把复制矩阵的结果写回原矩阵。Python 实现大概长这样def setZeroes(matrix): m, n len(matrix), len(matrix[0]) copy [row[:] for row in matrix] for i in range(m): for j in range(n): if copy[i][j] 0: for k in range(m): matrix[k][j] 0 for k in range(n): matrix[i][k] 0这个方案能正确解决问题因为它把“检测”和“执行”完全分开了检测时看的是复制矩阵执行时改的是原矩阵互不干扰。但它的缺点也明显空间复杂度 O(mn)一个 n 行 m 列的矩阵就要额外开一份同样大小的内存。如果矩阵是 1000×1000你得多存 100 万个整数。刷题时这么写没问题但面试时如果就此打住空间优化那部分分就丢了。我认为这个版本存在的价值只是作为讨论的起点帮助确认你已经理解了题目的基本规则。2.2 解法二两个标记集合空间 O(mn)仔细想一下最终哪些位置会变成 0完全由两个独立的信息决定这一行里是否存在 0这一列里是否存在 0。某个位置 (i,j) 会被清零当且仅当第 i 行有 0 或者第 j 列有 0。所以根本不需要记录矩阵里每一个 0 的位置只需要记录两件事哪些行有 0哪些列有 0。用两个布尔数组或者两个集合存就行。def setZeroes(matrix): 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(mn) 的空间直接降到了 O(mn)这是一个很大的跨越。而且在很多真实工程场景下这个方案其实比 O(1) 版本更实用。比如矩阵轮廓信息、图像数据里的零值标记开两个长度分别为行数和列数的布尔数组成本很低代码可读性也高。如果面试官没有特殊要求果断写这个版本是稳的。2.3 解法三把第一行和第一列当成标记板空间 O(1)空间还能不能继续压缩O(mn) 已经跟矩阵的规模线性相关了想要常数空间就只能从“把信息塞回原矩阵”这条路上想办法。注意一个事实矩阵第一行有 n 个格子第一列有 m 个格子这些格子本来就是矩阵的一部分。我们可以把“第 j 列是否需要清零”这个状态存到 matrix[0][j] 上把“第 i 行是否需要清零”这个状态存到 matrix[i][0] 上。这样就用矩阵自己的边界空间完成了标记不需要额外申请任何数组。但这里有一个非常容易忽略的冲突点matrix[0][0] 这个格子同时处于第一行和第一列。如果它被用来代表“第 0 列是否有 0”那你就不再有地方存放“第 0 行是否有 0”的状态反过来也一样。所以必须用两个额外的布尔变量先把第一行、第一列本身的状态单独记下来再把剩余的行列信息写进边界。整个过程拆成四步记录第一行是否存在 0记录第一列是否存在 0。从 (1,1) 开始遍历矩阵内部遇到 0 就更新边界标记matrix[i][0] 0matrix[0][j] 0。再次从 (1,1) 开始遍历根据边界标记把内部元素清零如果 matrix[i][0] 0 或者 matrix[0][j] 0就把 matrix[i][j] 置为 0。最后根据第一步记录的两个变量单独处理第一行和第一列。下面这个表格可以帮你快速对比三种解法的定位解法空间复杂度核心思路适用场景复制矩阵O(mn)空间换简单只求快速通过两个标记数组O(mn)行与列独立记录工程中最常用第一行第一列标记O(1)原矩阵边界当白板面试进阶考察点3. 核心实现细节原地置零的完整流程3.1 完整可运行代码先给 Python 版本这是我在 LeetCode 上常用的写法class Solution: def setZeroes(self, matrix: List[List[int]]) - None: m, n len(matrix), len(matrix[0]) first_row_zero False first_col_zero False # 第一步单独记录第一行和第一列本身是否有0 for j in range(n): if matrix[0][j] 0: first_row_zero True break for i in range(m): if matrix[i][0] 0: first_col_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_zero: for j in range(n): matrix[0][j] 0 if first_col_zero: for i in range(m): matrix[i][0] 0C 版本也一并给出方便在不同语言习惯下互相对照class Solution { public: void setZeroes(vectorvectorint matrix) { int m matrix.size(); int n matrix[0].size(); bool 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; } } } };代码看起来不长但每一步都有明确目的。第二步扫描范围是 (1,1) 到 (m-1,n-1)刻意避开第一行和第一列第三步同样避开边界。这个“避开”不是可有可无的细节而是整个方案成立的关键。3.2 为什么标记信息不会在置零过程中被破坏很多人第一次看到这个解法时都会有疑问边界上的 matrix[i][0] 和 matrix[0][j] 也是矩阵的一部分等会儿执行清零时这些标记位置不也会被清零吗标记被清掉了第三步的信息从哪来答案在于执行顺序。仔细看代码第二步写标记的时候只遍历内部区域不碰第一行和第一列。第三步读标记清零的时候读的是 matrix[i][0] 和 matrix[0][j]改的是 matrix[i][j]也没有去动边界。只有当前三步做完之后第四步才会去处理第一行和第一列本身。到那时候内部元素该清的已经清完了边界被改成什么样都无所谓了。我建议你手动模拟一个例子来加深理解。用这个矩阵1 2 3 4 0 6 7 8 9先记录第一行没有 0第一列也没有 0所以 firstRowZero falsefirstColZero false。第二步发现 (1,1) 位置是 0于是把 matrix[1][0] 改成 0把 matrix[0][1] 改成 0。矩阵变成1 0 3 0 0 6 7 8 9第三步遍历内部元素凡是 matrix[i][0] 0 或者 matrix[0][j] 0 就清零。第 1 行的行标记已经变成 0所以整第 1 行被清零第 1 列的列标记也已经变成 0所以第 1 列被清零。最终1 0 3 0 0 0 7 0 9完美匹配预期结果。再试一个第一行本身带 0 的例子0 2 3 4 0 6 7 8 9第一步记录 firstRowZero truefirstColZero true因为 (0,0) 本身是 0。第二步从 (1,1) 开始扫发现 (1,1) 是 0把 matrix[1][0] 和 matrix[0][1] 都改成 0。此时矩阵0 0 3 0 0 6 7 8 9第三步清零内部后矩阵变成0 0 3 0 0 0 7 0 9第四步因为 firstRowZero 为 true第一行整行清零firstColZero 为 true第一列整列清零。最终0 0 0 0 0 0 0 0 0结果对不对左上角 (0,0) 本身是 0它会让第一行和第一列全部清零内部 (1,1) 是 0会让第 1 行和第 1 列全部清零。四个角落和两条中间轴全部覆盖确实整个矩阵都该是 0。逻辑自洽。3.3 边界情况处理要点LeetCode 官方的约束通常保证了矩阵至少一行一列但写代码时还是要有防御意识。如果 m 或 n 可能为 0len(matrix[0]) 会直接越界。可以在函数开头加一句if not matrix or not matrix[0]: return单行矩阵的情况比如 [[1,0,1]]。第一步扫描第一行时firstRowZero 会被置为 true。第二步和第三步的循环因为 m 等于 1range(1, m) 为空自然跳过。最后第四步把第一行整行清零结果是 [[0,0,0]]。这符合题意。单列矩阵的情况同理。比如1 0 1firstColZero 为 true最后整列清零。全非 0 矩阵的情况最省心所有标记都不触发矩阵原样返回。全 0 矩阵则所有标记都触发结果整个矩阵全 0也正确。4. 常见问题与排查实录4.1 高频错误盘点我把实际写代码过程中最容易出的四个错误整理成一张表每条都是真实踩过的坑错误类型错误现象根因分析解决方案边扫边改矩阵里的 0 越滚越多几乎全变 0检测和修改混在一起新产生的 0 参与后续判断先收集标记再统一执行忽略 matrix[0][0] 冲突首行或首列被错误清空matrix[0][0] 同时代表行标记和列标记状态用两个额外布尔变量单独记录清零时从 (0,0) 开始遍历标记被提前清掉后续列全部失效内部清零阶段碰了第一行第一列第二步和第三步都从 (1,1) 开始下标写反某行被清成了列某列被清成了行matrix[i][0] 和 matrix[0][j] 混用写完后逐行检查索引 i/j 的位置其中“边扫边改”是最初级的错误。比如你在遍历时遇到一个 0立刻把整行整列清零但后面还没遍历到的位置已经被你改成了 0程序会以为那里原本就是 0于是继续清零它的整行整列。一轮扩散下来结果就是大面积误伤。“忽略 matrix[0][0] 冲突”也很隐蔽。假如第一行存在 0 但第一列不存在 0如果你只用 matrix[0][0] 来进行边界判断就会把第一列也错误清空。因为 matrix[0][0] 既记录了行的信息也参与了列的信息推导。“清零时从 (0,0) 开始遍历”是我自己当初犯过的错。我当时写第三步时很顺手地用了双重 for 从 0 开始结果第一步刚把 matrix[0][j] 标记写进去第三步一上去就把这些标记清零了。后面的元素再也读不到列信息结果大面积漏清。4.2 自测用例与排查技巧提交代码之前我建议先跑下面这一组用例覆盖各种典型场景用例1 [[1,1,1], [1,0,1], [1,1,1]] 预期 [[1,0,1], [0,0,0], [1,0,1]] 用例2 [[0,1,2,0], [3,4,5,2], [1,3,1,5]] 预期 [[0,0,0,0], [0,4,5,0], [0,3,1,0]] 用例3 [[0,1]] 预期 [[0,0]] 用例4 [[1], [1], [0]] 预期 [[0], [0], [0]]用例 2 比较典型它同时包含首尾两个 0会触发第一行和最后一列的清零内部还有独立的 0 触发中间列能很好地检验边界标记和内部标记是否冲突。排查时我有一个习惯在标记阶段结束后和执行阶段结束后分别打印一次矩阵。第一次打印可以看到第一行和第一列是否被正确改写成了“标记集合”第二次打印可以确认清零是否只影响了该影响的行列。这一步能快速定位绝大多数索引错误。4.3 面试追问与扩展思考如果你把 O(1) 解法写出来了面试官很可能会继续追问或者换场景考察。常见的问题方向有几个第一个方向是“为什么 O(1) 空间是可行的”。本质原因是行信息有 m 个、列信息有 n 个这些信息恰好可以映射到矩阵边界已有的 mn 个格子上不需要额外分配内存。第二个方向是“如果矩阵的内存特别珍贵不想破坏原数据怎么办”。这时可以讨论位图或者额外开一个长度非常小的标记数组。但要注意如果允许覆盖边界原地方案就是最优的。第三个方向是“如果矩阵很大但是 0 很少空间上有没有更灵活的做法”。这时候用两个稀疏的哈希集合可能更合适因为空间只跟 0 的个数相关而不是跟矩阵尺寸相关。虽然理论上空间复杂度还是 O(mn) 的上界但实际内存占用会小很多。第四个方向是相关题目的迁移。比如生命游戏这类题目同样要求在原数组上用标记位保存多个状态思路和这题一脉相承。做过这题之后再做生命游戏你会发现“把信息存回数组自身”这个套路是相通的。最后再说一个我个人的刷题体会。这道题我第一次做的时候五分钟就写完了复制矩阵版本当时觉得自己会了。后来在一次模拟面试里被要求优化到 O(1)我才意识到自己只是“会跑通”不是“会想透”。真正把第一行第一列标记法理解清楚之后最大的收获不是背下了这题的代码而是建立了一种空间优化直觉当题目不允许你开额外空间时先看看数据本身有没有没被利用起来的位置再想想操作顺序怎么设计才能保证标记不被提前销毁。带着这个思路去刷后续的原地修改类题目你会顺手很多。
