力扣73题和74题这两道题其实非常适合放在一起刷。一个是原地修改矩阵、考状态标记的技巧另一个是二分查找在二维结构上的变形应用。表面上一个考数组操作、一个考查找算法但做完之后你会发现它们都在反复敲打同一件事你对二维矩阵下标的控制到底熟不熟。很多人在二维矩阵题上吃亏不是算法思路想不到而是坐标转换、边界处理、空间复用这些细节上栽跟头。这篇文章就用这两道题把这些问题一次捋清楚。1. 两道题放在一起刷的原因它们都卡在矩阵坐标控制上先说结论73题和74题的核心考点完全不同但解题时的思维瓶颈高度重合——你是怎么把一个二维位置映射到另一个二维位置又是怎么把一个线性位置展开成二维坐标的。73题是给矩阵中值为0的元素所在的整行和整列全部置0这需要你在空间复杂度受限的情况下记录哪些行哪些列要被清零。这里面的核心难点不是要不要清而是用什么标记来清。74题是在一个行列都单调递增的矩阵里搜索目标值两种主流解法里一种需要把二维坐标转成一维下标再用标准二分查找另一种需要根据中间位置反推出mid对应的行和列。这里面的核心难点也不是二分怎么写而是一个index怎么拆成(row, col)。你品一下这两道题一个是要把二维信息压缩到一维去记录73题的首行首列复用另一个是要把一维下标展开成二维坐标去取值74题的二分查找。方向相反但底层都在训练同一套坐标换算能力。连续刷完这两题你对matrix[row][col]和row、col之间关系的直觉会明显不一样。另外这两题的“姿势水平”也合适。73题属于中等偏下难度思路一旦开窍代码量不大74题的不同解法复杂度差异明显适合用来理解二分查找的两种模板写法。一个偏思维一个偏实现凑在一起刚好互补。以下默认你使用的语言是C核心思路对所有语言通用。2. 第73题矩阵置零O(1)空间解法的核心思路与常见坑题目要求很简单给定一个 m x n 的矩阵如果某个元素是 0就把该元素所在的行和列全部置为 0。进阶要求是尽量用常数空间解决。暴力做法当然是人人都能想到的新开一个同样大小的矩阵遍历原矩阵把每个0映射过去最后把新矩阵写回原矩阵。这是O(mn)的额外空间虽然能过但面试里一旦追问“能不能把空间降下来”就暴露了。另一个常见思路是用两个数组记下哪些行有0、哪些列有0再次遍历时根据数组决定是否置0。空间复杂度O(mn)比O(mn)好很多但还不是最优。真正的O(1)方案是复用矩阵自身的信息来当标记。2.1 为什么能用首行首列当标记核心观察是某个格子matrix[i][j]如果为0最终结果里第i行和第j列都要被清零。那我就不需要为了记住“这个0会影响第i行和第j列”这件事额外开辟空间只要把信息写回矩阵自身即可——具体来说就是利用第0行来标记哪些列需要清零利用第0列来标记哪些行需要清零。听起来很妙但有一个致命细节如果直接把matrix[i][0]和matrix[0][j]当成标记位那第0行和第0列本身作为“数据”也被污染了。比如matrix[0][0]这个格子它同时是第0行第0列的标记位和前几个元素的真实数据信息直接冲突。解决方式是在动手之前先把第0行、第0列是否含0的原始信息保存下来最后单独处理这两行两列。这就是网上很多题解里“先扫描第0行和第0列再扫描内部区域最后根据标记和保存结果回写”的流程。2.2 一个标记方案放在实际实现中容易踩的坑这里有一个看起来不起眼但实战中非常容易错的地方扫描顺序。很多人按“先扫描整个矩阵边扫边改标记然后统一清行清列”的思路写结果发现标记位在扫描过程中被改掉了。举个例子。你从头遍历矩阵准备把第i行有0的信息记录到matrix[i][0]这时候如果第j列恰好是0你的标记动作会把matrix[i][0]改成0但下一次遍历到matrix[i][0]本身时它已经是0了你会误以为“第0列也需要清零”导致后续整个第0列被错误清零。这类问题其实是二维遍历中非常典型的“写操作影响后续读结果”的并发冲突错觉。因为矩阵是原地操作的而你又在同一个矩阵上做标记和读取顺序一旦不对信息就串了。正确的做法是先记录第0行和第0列的原始状态然后从第1行第1列开始扫描内部区域只对内部元素做标记。这样标记动作不会干扰到后续扫描的原始数据因为整个内部区域不会再被当作“原始数据”去读取。2.3 实现代码与逐行注释void setZeroes(vectorvectorint matrix) { int m matrix.size(); int n matrix[0].size(); bool row0 false, col0 false; // 记录第0行和第0列是否有0 for (int j 0; j n; j) { if (matrix[0][j] 0) row0 true; } for (int i 0; i m; i) { if (matrix[i][0] 0) col0 true; } // 用内部元素的情况来标记哪些行和列需要清零 // 注意这里i和j都从1开始 for (int i 1; i m; i) { for (int j 1; j n; j) { if (matrix[i][j] 0) { matrix[i][0] 0; // 标记第i行 matrix[0][j] 0; // 标记第j列 } } } // 根据标记将内部区域清零 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; } } } // 最后根据保存的原始状态单独处理第0行和第0列 if (row0) { for (int j 0; j n; j) matrix[0][j] 0; } if (col0) { for (int i 0; i m; i) matrix[i][0] 0; } }这段代码的执行顺序非常关键第一遍先记录原始状态第二遍遍历内部区域做标记第三遍根据标记清内部区域第四遍清首行首列。四步顺序错一步结果就是错一片。2.4 另一种边界情况如果首行首列本身就需要清零有的题解会把标记和首行首列的处理合在一起用两个布尔变量来记录首行首列是否要清零然后先处理首行首列再处理内部区域。这种写法也能过但我在实际测试中觉得上面的写法逻辑更直观——先记住原始状态再逐步处理每一步的输入输出都很清晰不容易被绕晕。不过你要注意上面的写法有一个前提只适用于没有负数、没有特殊值干扰的情况。如果矩阵里允许存在任意整数那么所有数字都可能变成0标记位的值在和原数据区分时需要格外小心。我在测试里试过把标记值改成INT_MAX结果原数据里真有INT_MAX直接翻车。所以用矩阵本身做标记时最稳的还是“用第0行和第0列的原始数据来做标记”而不是“用一个特殊值来标记”因为特殊值可能和原始数据冲突。3. 从暴力到O(1)的演进空间复杂度优化思路值得单独拉出来讲第73题如果只看题解几分钟就能抄完但我认为真正有价值的是把从O(mn)到O(mn)再到O(1)的整个空间优化过程走一遍。这个过程本身就是面试中“能不能对已有方案做优化”的考题。O(mn)的做法适合新手理解但没有优化意义略过。O(mn)的做法其实已经很接近最终解了它用两个一维数组分别记录有0的行和列这样就不需要额外二维数组。但O(1)的方案更进一步把这两个一维数组直接“映射”到矩阵的首行和首列上。这里面有一个思维转换为什么可以放心大胆地拿首行首列当数组用因为首行首列在整个算法中被赋予了双重身份。一方面它们是真实数据另一方面它们充当了标记位。只要在算法开始前把它们的“真实身份”备份好之后就可以安全地当作标记位使用了。这种“借用地盘”的思路在内存受限的场景比如嵌入式、单片机、GPU kernel里非常常见。顺便说一句这道题在真实工程里的应用还挺常见的。比如图像处理里的连通域标记或者表格数据清洗时遇到空值都需要把某些行列标记后整体清掉。你掌握了这个技巧处理这类问题时就能直接迁移。4. 第74题搜索二维矩阵为什么这道题本质上是一个一维问题和第73题对比74题的题干非常“二维”给定一个行列都递增的矩阵实现一个函数搜索目标值。但聪明的解法会告诉你这道题根本不需要二维的搜索算法——把它拉直成一维数组就是一个标准二分查找。为什么可以拉直因为题目给了一个很强的条件每一行的第一个整数大于前一行的最后一个整数。对不是简单的“每行递增、每列递增”而是行与行之间完全衔接。这样的矩阵按行拼接起来就是一个严格递增的一维数组。如果少了这个条件矩阵只是“行内递增且列内递增”那就不能直接拉直成一维二分了得用更复杂的搜索方式。所以74题真正的考点其实是“你读题的时候有没有意识到这个更强的条件以及如何利用它”。4.1 二维下标与一维下标的换算公式假设矩阵是 m 行 n 列。如果把它展开成一维下标 index 的范围是 0 到 m*n-1。那么第 index 个元素所在的行 row index / n第 index 个元素所在的列 col index % n反过来一个位置 (row, col) 在一维中的下标就是 row * n col这三个公式是整个74题的精髓。你只需要把二分查找里的 mid 换一行一列就完成了二维到一维的映射。我用实际案例验证一下。假设矩阵是1 3 5 7 10 11 16 20 23 30 34 60m3n4。二分查找第一次 mid (011)/2 5对应 row5/41col5%41即 matrix[1][1] 11。如果 target16因为 16 11所以 leftmid16。第二次 mid(611)/28row8/42col8%40即 matrix[2][0]23。target16 23所以 rightmid-17。第三次 mid(67)/26row6/41col6%42即 matrix[1][2]16。命中。这个过程中你唯一要做的就是除法取整和取余别忘记列数n是除数。4.2 标准二分模板与mid指针的移动逻辑二分查找的模板网上很多但很多新手在写的时候会把 left、right 和 mid 的边界条件搞混。我分享一个我自己一直在用的模板bool searchMatrix(vectorvectorint matrix, int target) { int m matrix.size(); if (m 0) return false; int n matrix[0].size(); int left 0, right m * n - 1; while (left right) { int mid left (right - left) / 2; int row mid / n; int col mid % n; int val matrix[row][col]; if (val target) { return true; } else if (val target) { left mid 1; } else { right mid - 1; } } return false; }这个模板的关键点是 while (left right)它保证循环退出时一定是因为left right此时查找区间为空。如果你写成 left right边界条件处理起来会更绕容易在只剩一个元素时漏判。用left (right - left) / 2而不是(left right) / 2是为了防止整数溢出。在算法题里你可能觉得 m*n 不会多大但工程习惯应该一开始就写好。4.3 为什么说74题还有第二种常规思路以及它的问题所在除了“拉直成一维二分”之外很多人还会想到第二种思路先用二分查找定位所在的行再在那一行里做二分。这个思路也是对的因为矩阵每一行内部递增并且行与行之间也衔接。做法是先对每行的“最后一个元素”做二分找到第一个最后一个元素大于等于 target 的行再在这一行里对 target 做二分这个思路本质上也是二分但代码量更大而且容易忽略一种边界情况如果 target 比某行最后一个元素大但又比下一行第一个元素小那么它可能落在行之间的空隙里。虽然因为行与行衔接的强条件这种间隙在实际展开的一维数组里是不存在的但在“先找行再找列”的路径中你需要额外处理这种边界。我个人的建议是首选“一维二分”因为逻辑最少、最难出错。但第二种思路作为理解矩阵结构的辅助练习也值得动手写一写。4.4 边界条件与空矩阵、一行矩阵等特殊情况这道题边界条件不多但容易卡点有两个空矩阵matrix 为空时直接返回 false不然 matrix[0] 会越界。一行矩阵此时 row mid / n 中 n 就是列数如果只有一行n 就是这一行的长度。公式依然成立但千万别把 n 和 m 搞混。还有一个容易被忽略的如果 target 不在矩阵里但值介于两个元素之间二分会正常退出并返回 false。这个场景验证过没问题。5. 两题联动的总结性思考二维矩阵操作的三个方法论做完这两道题我复盘了一下可以总结出三个方法论级别的点。你之后刷任何二维矩阵题都可以拿这三点先自检一下。第一二维矩阵的坐标换算能力是基础中的基础。无论是用一维下标映射二维坐标还是反过来用两个一维数组记录行列状态本质上都是在做同一种换算。先把 row、col 和 index 三者之间的公式写熟很多题目就赢在了起跑线上。第二原地修改矩阵时必须警惕“数据读取与写入的顺序冲突”。第73题是经典中的经典标记位和原始数据共用空间顺序错了全盘皆输。实战中我习惯在动手前先画一张“状态流转表”把每一步会修改哪些位置、修改之后哪些位置的读值会受影响标出来比直接写代码靠谱得多。第三遇到二维搜索时先读题找有没有“强条件”。74题能变成一维二分靠的是“每行的第一个整数大于前一行的最后一个整数”这个强条件。如果只有行列递增而没有行间衔接就得考虑别的算法了。读题时多花30秒找这个条件比写代码时多花30分钟调试划算。6. 相关高频变形题与延伸方向如果把73题和74题做扎实了遇到下面这些变形会轻松不少。与73题类似的是“只记录第一次出现的位置”类问题比如力扣289题生命游戏也是原地更新矩阵、需要同时读写旧状态和新状态再比如力扣36题有效的数独需要判断行、列、小块内是否有重复元素。它们都用到了“标记”的思路只是标记的方式不同。与74题类似的是力扣240题搜索二维矩阵II。区别在于240题的矩阵只保证每行递增、每列递增没有行间衔接这个强条件。这时候就不能拉直成一维二分了而是要用“从右上角出发逐步缩小搜索范围”的Z字形搜索。细心对比74和240的题干差异能帮你更深刻地理解“条件决定算法”。更进一步如果你把矩阵的”二分“思想推广到多维那就是力扣378题有序矩阵中第K小的元素。那题用到了“二分答案”的思路与74题的静态查找不同但都有二分查找的影子。这些题我建议你在刷完73、74之后按顺序接着刷。连续几道二维矩阵题下来你对坐标换算、边界控制、原地操作这三大基本功会形成肌肉记忆。7. 刷题过程中的效率工具与习惯分享你可能好奇为什么要把这两道题反复复盘这么多遍。其实刷题这件事刷多少题不是目的刷完能留下来多少才是目的。我自己的习惯是每道题刷完都会整理一份“错点清单”记录这次哪里卡壳、下次要注意什么。73题我记录的是“扫描顺序”74题我记录的是“mid拆行拆列时不要用m做除数”。如果你也在刷题可以在本地搭建一个简单的笔记模板每次刷完记录几个固定字段题目编号与名称我的核心思路一两句话概括代码实现核心片段错点与注意点这次踩的坑复杂度分析相关题目链接这样坚持一段时间你会发现自己的进步是可量化的。而且再次复习时只需要看错点清单就行不需要把整道题重新做一遍。至于刷题环境我个人比较推荐在本地编译器里写完整代码再提交而不是直接在线编辑。因为本地编译能让你看到具体哪一步内存越界、哪个变量没有初始化调试效率高很多。这两道题一个是O(1)空间的艺术一个是二分查找的工程化应用刷透之后对二维矩阵题型的底气会足很多。如果你现在正卡在某道矩阵题上不妨回头先把这两题的代码默写一遍再去做那题会有种豁然开朗的感觉。