最近我在集中刷力扣的二维矩阵题第73题和第74题刚好是一对很有意思的组合一个要求原地修改矩阵一个要求高效查找矩阵中的目标值。标题看着都是“二维矩阵”但背后的考察点完全不同一个考验你对空间的使用能不能抠到常量级一个考验你能不能把二维结构抽象成一维有序数组。这两道题刷完之后我对矩阵下标的敏感度和边界处理能力都有了明显提升所以专门把笔记整理出来给同样在刷题的朋友做个参考。这篇笔记适合正在准备面试、集中刷数组/矩阵题的读者也适合想补一补二分查找和原地算法基本功的人。1. 为什么要把73和74放在一起刷1.1 两道题到底在考什么先分别看一下题目本身。第73题是“矩阵置零”给一个 m x n 的矩阵如果一个元素是 0就把它所在的整行和整列都变成 0并且要求原地修改不能用额外的大块内存去复制矩阵。这个题目表面上是“改数”实际上考的是状态记录你要在遍历过程中记住哪些行、哪些列出现过 0最后再根据这些记录把对应位置刷成 0。第74题是“搜索二维矩阵”给一个行内从左到右升序、且每一行第一个数都比上一行最后一个数大的矩阵判断目标值 target 是否存在。这个题目表面上是查找实际上考的是二分查找能不能从一维数组平移到二维矩阵。两题放在一起刷的好处是互补73题逼你思考怎么用更少的空间记录信息74题逼你思考怎么用更高效的方式定位信息。如果在力扣上连续刷这两题你会发现它们有个共同的隐藏考点对行列坐标的理解。73题里你必须清楚每个 0 落在哪一行、哪一列才能正确置零74题里你必须会在一维下标和二维行列之间来回换算才能实现一次二分。很多人在二维矩阵题上栽跟头其实不是算法不会而是 row 和 col 算反了或者 m 和 n 弄混了所以把这两道题放在一起正好能专门练这块基本功。1.2 刷完这两题能带走的能力第一个收获是空间复杂度的敏感度。73题最朴素的写法是复制整个矩阵空间复杂度 O(mn)但面试里几乎必然会被追问能不能优化。从 O(mn) 到 O(mn)再到 O(1)这一路优化本身就是一套标准的空间压缩思维训练。刷完之后你会慢慢养成一个习惯拿到一道需要记录状态的题先问问自己这个状态能不能塞进现有的数据结构里而不是无脑开新数组。第二个收获是二分查找的推广能力。74题不是让你二分某个一维数组而是让你意识到当矩阵满足“行内递增且行间衔接递增”时它本质上就是一段排好序的一维序列。能把一个看起来是二维的问题归约成熟悉的一维问题这是刷题更想练出的能力而不是背住某一道题的代码。第三个收获是边界情况意识。二维矩阵题的坑非常集中单行、单列、第一行有 0、第一列有 0、目标值在序列开头或结尾、矩阵只有一个元素。73题和74题正好把这些边界场景都覆盖到了。刷完之后你会形成一种条件反射看到矩阵题先问 m 和 n 是否可能为 0第一行第一列要不要特殊处理。这个条件反射在面试里特别值钱。2. 力扣第73题矩阵置零2.1 看完就能写的O(mn)空间版先回忆题目给定一个 m x n 的矩阵 matrix如果一个元素为 0则将其所在行和列的所有元素都设置为 0。请使用原地算法。示例里最经典的是matrix [[1,1,1],[1,0,1],[1,1,1]]中间的 0 会把第二行和第二列全部变成 0输出是[[1,0,1],[0,0,0],[1,0,1]]。一个完全不需要动脑的方案是复制一份矩阵然后遍历原矩阵遇到 0 就在副本里把整行整列置零最后把副本复制回去。这个方案空间是 O(mn)虽然能通过但显然不是题目想考察的。稍微好一点的是用两个长度为 m 和 n 的布尔数组rowZero[i]表示第 i 行是否出现过 0colZero[j]表示第 j 列是否出现过 0。先遍历整个矩阵只记录不修改第二遍遍历时发现rowZero[i]或colZero[j]为 true就把matrix[i][j]改成 0。这样空间复杂度是 O(mn)。def setZeroes(self, matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) rows [False] * m cols [False] * n for i in range(m): for j in range(n): if matrix[i][j] 0: rows[i] True cols[j] True for i in range(m): for j in range(n): if rows[i] or cols[j]: matrix[i][j] 0这个版本正确性很高也容易理解。面试时优先说这个方案是因为思路清楚、不容易出错。但面试官一般会接着问“能不能把额外空间降到 O(1)”这时候就要进入下一步。2.2 原地改造的核心用第一行和第一列做标记O(1) 空间版本是这题的精髓。先说关键观察我们真正需要保存的信息无非是“第 i 行要不要清零”和“第 j 列要不要清零”。既然矩阵本身就有 m 行 n 列为什么不直接用第一行保存每一列的标记、用第一列保存每一行的标记呢也就是说如果matrix[i][j] 0就令matrix[i][0] 0和matrix[0][j] 0。第一轮遍历结束后第一行和第一列上被写下的 0就在代替那两个布尔数组记忆信息。这个方案听起来很妙但有一个很隐蔽的坑第一行和第一列既是标记位也是真正的数据位。比如原矩阵的第一行本身就有 0那这个 0 会被后续的标记行为覆盖或混淆。所以需要在开遍历之前先用两个变量记录第一行和第一列原本有没有 0。流程可以拆成四步先记录firstRowHasZero和firstColHasZero。从第 1 行、第 1 列开始遍历整个矩阵跳过第一行第一列遇到 0 就把对应行标记写到matrix[i][0]列标记写到matrix[0][j]。根据第一行、第一列上的标记把第 1 行到第 m-1 行、第 1 列到第 n-1 列中的对应位置置零。最后回头处理第一行和第一列如果firstRowHasZero为真整行置零如果firstColHasZero为真整列置零。这里要特别提醒第 3 步和第 4 步的顺序不能反。如果先处理第一行或第一列就可能把第一行第一列上的标记清掉后面想用就没得用了。我第一次自己实现时就是顺序写反导致输出结果错乱。正确的做法是把第一行、第一列的“收尾”留到最后。写成代码长这样def setZeroes(self, 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(1)只多了两个布尔变量。也可以进一步精简比如用matrix[0][0]表示第一列状态再用一个变量表示第一行状态但在面试中代码可读性和思路清晰比炫技重要。我建议用两个变量分别表示别人一眼就能看懂你的设计意图。2.3 边界用例与我的踩坑记录我把这题当练习题敲了几组容易错的输入[[0]]只有一个元素且为 0输出应该还是[[0]]。此时firstRowHasZero和firstColHasZero都为 true最终两层处理都会执行结果仍为[[0]]。[[1]]没有 0输出保持不变。[[1,0]]一行两列第二个元素为 0。第一行有 0第一列没有 0最后第一行整行置零结果是[[0,0]]。单列矩阵[[1],[0]]第一列有 0最后第一列整列置零结果是[[0],[0]]。矩阵中 0 同时出现在第一行和第一列例如[[0,1],[1,1]]两个哨兵变量都为 true最终第一行和第一列都变成 0结果[[0,0],[0,1]]。我踩过的坑主要集中在这几个地方第一在标记阶段把 i 和 j 的范围写成从 0 开始导致matrix[0][0]被提前污染第二在根据标记置零时没有跳过第一行第一列于是把第一列的错误状态又扩散到整列第三最后处理第一行和第一列时没有判断firstRowHasZero和firstColHasZero而是直接对第一行第一列置零导致原本没有 0 的边界行也被错误清零。这个“先记录后修改”的思路在工程里也很常见。比如你要在不申请新内存的前提下更新一个大表格的数据又需要保留一些旧状态作为参考本质上也是用类似思路去设计标记位。所以这道题不吃亏做完一遍空间优化的意识会明显强很多。3. 力扣第74题搜索二维矩阵3.1 暴力方向和“把二维拉直”的直觉第74题描述很清爽给定一个 m x n 的矩阵 matrix 和一个目标整数 target矩阵满足两个条件每行从左到右升序每行的第一个整数都大于上一行的最后一个整数。请判断 target 是否存在于矩阵中并尽量高效。示例matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]]target 3 时返回 truetarget 13 时返回 false。最直白的做法是两层循环暴力找复杂度 O(mn)。稍微优化一下因为每一行是有序的可以先遍历每一行对每一行做一次二分复杂度是 O(m log n)。但题目隐含的数据特征其实更强第一行最后一个数是 7第二行第一个数是 107 10也就是说行与行之间的数也是接续有序的。整个矩阵从左到右、从上到下连起来看就是一段连续升序序列。一旦意识到这点最简单高效的方法就浮现出来了把二维矩阵“拉直”成一个长度为 m*n 的一维数组直接二分。这里说的“拉直”不是真的创建一个新数组那空间又变大了。而是通过下标换算去虚拟地访问。比如一维下标 idx 对应的行是idx // n列是idx % n。这个换算非常关键也是这题真正想考察的。理解了这一点代码写起来反而比两次二分还短。3.2 一次二分的代码与坐标映射细节把矩阵看成虚拟一维数组后二分就变得非常标准。用 left 指向 0right 指向 m*n - 1mid 取中间位置。每次拿matrix[mid // n][mid % n]和 target 比较。如果相等就返回 true小于 target 时说明左半边都不用看left mid 1大于 target 时说明右半边都不用看right mid - 1。循环结束后没找到就返回 false。def searchMatrix(self, matrix, target): if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) left, right 0, m * n - 1 while left right: mid (left right) // 2 row mid // n col mid % n value matrix[row][col] if value target: return True if value target: left mid 1 else: right mid - 1 return False这段代码最需要注意的就是 n 不能为 0。虽然题目通常保证矩阵非空但在实际面试中你还是要先跟面试官确认 m 和 n 可能是 0 吗。如果不做防御matrix[0]会直接抛异常所以我在代码开头加了if not matrix or not matrix[0]的返回。另外有人喜欢用(left right) // 2有人喜欢用left (right - left) // 2。两种写法在普通长度下没有区别但我更推荐后一种写法因为它在数字很大时能避免一些语言的整数溢出问题也显得更规范。这个习惯可以统一到所有二分代码里。3.3 两次二分的另一种思路如果一次性二分让你觉得需要绕一层坐标映射这题还有另一种常见解法先在矩阵的第一列中做一次二分找到“最后一个小于等于 target 的行”然后再在该行内做一次普通二分。这种思路把二维问题拆成两个一维问题每一步都更直观。第一次二分的细节是要在第一列中找到最后一个满足matrix[row][0] target的行号。如果整个矩阵都没有这样一行说明 target 小于第一列的最小值直接返回 false。随后对找到的那一行做普通二分判断 target 是否在该行中出现。还是用例子说明。matrix 第一列是[1, 10, 23]如果 target 3最后一个小于等于 3 的是第 0 行然后在第 0 行里二分找到 3如果 target 11最后一个小于等于 11 的是第 1 行在第 1 行中找到 11如果 target 25最后一个小于等于 25 的是第 2 行但第 2 行里找不到 25最终返回 false。这个过程很容易理解也不容易写乱。两次二分的复杂度同样是 O(log(mn))因为第一次二分是 O(log m)第二次是 O(log n)两者相加量级上跟一次二分一致。一次二分的代码更短但两次二分在思路上更容易讲明白尤其适合在面试初期展示你对“行定位”和“列定位”的不同理解。如果面试官没有特别要求讲两次二分其实是更稳妥的沟通策略。3.4 二分边界处理与实测用例边界处理是二分题的重灾区74题也不例外。我测试时列了几类用例target 小于矩阵第一个元素比如 matrix 第一个元素是 1target 0。二分里 value 一直大于 targetright 不断左移最后退出循环返回 false。target 大于矩阵最后一个元素比如最后一个元素是 60target 61。value 一直小于 targetleft 不断右移最终返回 false。target 恰好是每一行的第一个元素比如 10。二分在查找过程中 mid 可能不落在 10 上但最终会收敛到它。target 恰好是每一行的最后一个元素比如 7。这个位置是行与行之间的“接缝”最容易出错但只要用matrix[mid // n][mid % n]统一取值就不会有问题。单元素矩阵[[5]]target 5 返回 truetarget 6 返回 false。我还特意验证了一个容易忽略的点一维下标 mid 和列数 n 的关系。如果 n 是矩阵的列数那么idx // n得到行号idx % n得到列号反过来row * n col idx。这个恒等式在做矩阵压缩和解压缩时特别好用。可以把它当成一个模板记下来后面刷其他矩阵题时能省很多思考时间。4. 两道题做完总结一套二维矩阵题打法4.1 坐标变换idx、row、col之间的换算二维矩阵题最烦的一点就是坐标换算。常见场景就是把二维数组看成一维数组处理或者反过来把一个有序的一维数组重新组织成二维矩阵。这时候只要记住一个核心公式idx row * n col其中 n 是矩阵的列数。反过来row idx // ncol idx % n。我在刷 74 题时深刻体会到这个换算如果刻在脑子里很多看起来需要复杂记忆的题都能简化。这个公式之所以重要还有一个原因是 73 题也要依赖行号、列号的概念但方向不一样。73题里我们不需要把二维压缩到一维而是要判断“某个位置属于哪一行、哪一列”本质上也是在做下标语义的切换。刷题遇到二维矩阵时先问自己一句我现在的操作是在按行遍历、按列遍历还是在按下标映射先把这一步想清楚写代码时会顺手很多。4.2 原地操作与额外空间的取舍73题的演进过程很典型一开始复制矩阵空间复杂度 O(mn)后来用两个标记数组空间复杂度 O(mn)最后用矩阵本身的第一行和第一列做标记配合两个变量记录哨兵空间复杂度才变成 O(1)。这个过程不是单纯的炫技而是大多数算法题里很常见的优化思路把信息存到原本就要使用的空间里减少额外的数据结构。但也要注意空间复杂度降低通常以代码复杂度提升为代价。在工程里如果矩阵很大、函数需要被频繁调用O(mn) 的额外空间往往也不是问题没必要为了常数级空间写出难以维护的代码。只有在面试中被明确要求“能否用 O(1)”时再去考虑这种写法。做题时先给出容易正确实现的版本再提出优化版本反而是更好的表达方式。我个人的判断标准是如果额外空间的量级和输入规模同一个级别通常值得尝试优化如果只是相差一个常数因子就不需要过度纠结。刷题和做工程不一样面试官更看重的是你能不能在正确性和效率之间找到合适的平衡点而不是一味追求最快最省。4.3 面试时的加分表达这两道题都是面试高频题特别是73题。如果面试官让你讲思路我建议你按这个顺序表达先说朴素解法复制矩阵或者用标记数组把思路讲清楚顺便说复杂度是多少。自己提出优化方向O(mn) 是因为我们用两个数组分别记录行和列的状态能不能把这个信息放进矩阵本身。引出第一行、第一列做标记的方案并主动说明为什么要先记录第一行第一列原本是否为 0。最后提一句边界单行、单列、全 0 矩阵你的算法都能正确处理。这个过程会让面试官看到你有优化意识同时知道坑在哪里。74题则更注重你对二分边界和下标的把握。如果可以在写代码前先口头描述“把二维拉成一维然后用标准二分”这样即使代码有小错面试官也更容易理解你的意图。很多人面试挂不是死在算法上而是死在“不讲人话”上这两题正好是练习表达的好素材。5. 延伸题单与刷题心得5.1 相关题目清单刷完73和74之后可以把下面这些题放到同一个刷题周期里搜索二维矩阵 II矩阵每行、每列分别升序但行与行之间不再整体有序因此不能直接用一次二分常见的解法是从右上角或左下角开始线性收缩复杂度 O(mn)。这道题能和74题形成很好的对比。螺旋矩阵 / 螺旋矩阵 II虽然不涉及查找和置零但同样需要精心维护边界能继续锻炼对二维坐标的控制。旋转图像要求原地旋转 90 度是原地算法在矩阵上的另一种应用值得和73题放到一起体会。有效的数独依赖行、列、子区域的坐标映射是下标换算的熟练工。矩阵中的最长递增路径把矩阵当图做 DFS能进一步训练二维结构的遍历思维。没必要一次性全刷完按两天一题、每道题都写清思路和代码的节奏走即可。关键是每做完一道题都回头看一眼它和 73、74 题有什么异同这种对比记忆比单独记题解牢固得多。5.2 我的一点刷题建议73和74都属于“看起来不难但想一次写对不容易”的题。我自己的体会是这类题目最适合用来练三个习惯一是写代码前先想清楚需要哪几个循环、每次循环在做什么二是写完代码后手动跑边界用例尤其是 m1、n1、第一行或第一列为 0 这类特殊情况三是给自己设一个时间限制如果在 15 分钟内没有完整思路就去看题解然后隔两天再独立重写一遍。这种“练完就复盘、复盘后再重写”的节奏比一遍遍刷简单题更有效。对我而言刷完这两道题最大的收获是看到二维矩阵题时我会有意识地去想“能否复用矩阵自身的信息”和“能否把矩阵看成有序数组”。这两个思维习惯已经不止一次帮我在新题里快速定位解法所以专门留下来写成笔记。如果你最近也在刷这类题建议你也试试把两道相似题放在一起对比消化效果会比单题刷要好不少。