搜索二维矩阵II最优解：从暴力遍历到Z字扫描的Python实现与边界处理

力扣hot100第21题搜索二维矩阵II是一道典型的“看着像二分、结果还有更妙解法”的算法题。我第一次做的时候直接用Python暴力遍历两层循环扫一遍矩阵提交完觉得太简单了后来看到题解区从右上角走Z字形的做法才发现原来最优解可以做到O(mn)。这两天重新整理这道题把Python版本的实现、边界条件、调试方法和常见坑都过了一遍有了不少新的体会。如果你正在刷力扣hot100、准备面试算法题或者刚学会Python的二维列表操作这篇文章应该能帮到你。1. 题目理解与核心思路1.1 题目到底在说什么先看输入。力扣给的矩阵长这样matrix [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]如果target是5返回True如果target是20返回False。这个矩阵有两个关键性质每一行从左到右递增每一列从上到下递增。但注意这不是一个全局有序的矩阵。比如第二行第三个数是8第一行第四个数却是118比11小说明“下一行的某个位置”不一定大于“上一行靠右的位置”。这种局部有序、全局乱序的特点决定了你不能简单地把二维矩阵拍平成一个一维数组再用一次二分查找搞定。很多人第一次看到这题会想到暴力遍历或者对每一行做一次二分。这两种方案都没错但都不是最优解。真正想清楚之后你会发现这题的精华在于找到一个“决策点”每次比较之后能确定性地排除一整行或者一整列。1.2 为什么会出现在hot100里力扣hot100收录的都是高频、高价值的题。搜索二维矩阵II所在的LeetCode 240这个题号在面试里出现的频率相当高因为它的门槛刚刚好暴力做很容易但说出O(mn)的解法就需要对矩阵结构有深入理解。这道题能考察的东西很多。第一它考二维有序数据的敏感度你能不能从“行列分别有序”这个条件里找到突破口。第二它考一题多解的能力暴力、二分、Z字形扫描、分治每个方案的复杂度差异很大面试官通过你的思路演进就能判断你的算法水平。第三它在代码实现上非常短但边界问题很多很适合在写代码时考察候选人的严谨程度。所以我在刷hot100的时候遇到这种“代码越短越要小心”的题都会专门停下来多做几个变体而不是看一眼答案就划走。1.3 关键观察从四个角看矩阵把矩阵想象成一张数表它的四个角分别有不同的“走势”从左上角出发向右和向下都是增大的如果当前位置小于target该往右还是往下两个方向都有可能无法判断。从右上角出发向左是减小的向下是增大的。如果当前位置大于target说明这一列往下肯定都更大所以可以排除当前这一列向左走如果当前位置小于target说明当前这一行往左肯定都更小所以可以排除当前这一行向下走。从左下角出发向右是增大的向上是减小的。反过来用同样可以排除行或列。从右下角出发向左和向上都是减小的如果当前位置大于target该往左还是往上同样无法判断。所以真正能当决策点的只有右上角和左下角。这个观察是整个题目的核心后面所有解法都是从这衍生出来的。起始位置相邻方向能否做出决策左上角右增、下增不能两个方向都比当前大右上角左减、下增能大则左小则下左下角右增、上减能大则右小则上右下角左减、上减不能两个方向都比当前小你可以把右上角看成一颗二叉搜索树的根节点向左走是搜索更小值向下走是搜索更大值每一轮都在缩小搜索范围。2. 三种解法逐层拆解2.1 暴力遍历先求对再求快最直接的办法就是两层循环把整个矩阵扫一遍def searchMatrix_brutal(matrix, target): for row in matrix: for value in row: if value target: return True return False时间复杂度是O(m*n)m是行数n是列数空间复杂度O(1)。这个解法最大的优点是简单不可能写错不管矩阵是不是有序都能工作。但它没有利用题目给的两个有序条件数据量一大就很容易超时。我建议不要跳过这一步。暴力解法的价值在于它可以作为一个“正确性基线”。你在本地写Z字形扫描的时候可以先随机生成一些矩阵用暴力方法验证结果是否一致。如果暴力返回True但优化解法返回False说明你的优化逻辑有问题。这种对拍思路在刷题阶段非常实用能帮你快速发现隐藏的边界错误。2.2 逐行二分把二维问题拆成一维问题既然每一行都是递增的那我可以对每一行分别做二分查找。这是从暴力到优化的第一步def searchMatrix_binary(matrix, target): if not matrix or not matrix[0]: return False for row in matrix: if row[0] target or row[-1] target: continue left, right 0, len(row) - 1 while left right: mid left (right - left) // 2 if row[mid] target: return True elif row[mid] target: left mid 1 else: right mid - 1 return False这里做了一点小优化每个行先看首尾如果这一行的最小值都比target大或者最大值都比target小这行肯定没有target直接continue跳过。时间复杂度是O(mlog n)空间O(1)。如果行数很多但列数很少也可以反过来对每一列做二分复杂度会变成O(nlog m)。你可以根据m和n的大小选择开销更小的方向。这个解法的缺点是它没有利用“每一列也有序”这个条件。每行单独二分相当于把二维信息只用了半边虽然已经能过题但还不是最优。2.3 右上角Z字形搜索最优解的长相从右上角出发每次比较当前元素和target当前元素等于target直接返回True。当前元素大于target说明这一列往下都比当前元素大更比target大排除当前列向左移动一列。当前元素小于target说明这一行往左都比当前元素小更比target小排除当前行向下移动一行。写成Python代码非常短def searchMatrix_z(matrix, target): if not matrix or not matrix[0]: return False rows len(matrix) cols len(matrix[0]) row 0 col cols - 1 while row rows and col 0: cur matrix[row][col] if cur target: return True elif cur target: col - 1 else: row 1 return False复杂度是O(mn)。因为每一轮循环row最多增加m次col最多减少n次加起来最多mn次比较不会出现两层循环。我刚开始看这个算法时总担心会不会漏掉答案。后来想明白一个类比这就像在一本按字母顺序排列的书架上找一本书你不会从第一本开始逐本看而是先看当前书脊上的字母发现目标字母比它小就往左走一列发现比它大就往下一行走。每次都能排除一片区域所以效率高。2.4 三种方案的横向对比解法时间复杂度空间复杂度代码量适合场景暴力遍历O(m*n)O(1)很短小矩阵、对拍验证逐行二分O(m*log n)O(1)中等行少列多或行多列少右上角Z扫描O(mn)O(1)很短面试和竞赛首选从代码量上看暴力最短Z扫描也不长。但Z扫描需要你对四个角的行为有清晰理解否则很容易把比较方向写反。面试时只要你能画出排除逻辑代码本身不是问题。3. Python实现细节与踩坑记录3.1 边界条件空矩阵真的很容易踩坑先看两行判断if not matrix or not matrix[0]: return False为什么必须这么写因为matrix可能是[]也可能是[[]]。当matrix是[]时直接访问matrix[0]会抛IndexError当matrix是[[]]时matrix本身不为空但第一行是个空列表没有任何元素可取所以必须检查matrix[0]。很多人会漏掉not matrix[0]导致在[[]]这种用例上报错。力扣的测试用例是包含[[]]的所以这个判断必须写。not matrix放前面可以利用Python的短路求值避免表达式后面的matrix[0]被错误执行。如果你写的Z扫描版本没有判断not matrix[0]可能在[[]]上也能通过因为cols0col-1while条件col 0不成立直接返回False。但逐行二分版本如果没做这个判断遇到[[]]时for row in matrix会拿到一个空list二分循环条件left right不成立也不会报错。不过这种“碰巧通过”的代码风险很大建议统一写上。3.2 while循环里的索引更新到底怎么写Z扫描的核心循环只有三行分支但方向写反的人非常多。记住一个原则你在操作的是matrix[row][col]第一个索引是行第二个索引是列。row 0 col cols - 1 while row rows and col 0: cur matrix[row][col] if cur target: return True elif cur target: col - 1 else: row 1col - 1是向左移动因为列号减小row 1是向下移动因为行号增大。有些同学初学时会写成row - 1导致无限循环或者漏解。如果用的是从左下角出发的写法则是row rows - 1 col 0 while row 0 and col cols: cur matrix[row][col] if cur target: return True elif cur target: row - 1 else: col 1两种写法都可以只要对应好方向逻辑。我个人更推荐右上角版本因为row和col的起始值比较直观不容易和矩阵下标的关系搞混。调试时可以加一句printwhile row rows and col 0: cur matrix[row][col] print(frow{row}, col{col}, value{cur})看到value的变化就能确认自己的移动方向是不是符合预期。3.3 二分查找的左右指针写法如果你选择逐行二分版本要注意闭区间的写法。我用的是left, right 0, len(row) - 1 while left right: mid left (right - left) // 2 if row[mid] target: return True elif row[mid] target: left mid 1 else: right mid - 1这里有几个容易踩的点。第一while条件要写left right不能写left right。因为在闭区间写法里当left right时当前这个位置还没有被检查过漏掉它可能会错过target。第二mid写成left (right - left) // 2虽然Python的整数不会溢出但这是一个通用好习惯。如果你用(left right) // 2在Java或C里遇到特别大的left和right可能溢出Python里没这问题不过为了统一习惯建议还是写前者。第三更新边界时left mid 1和right mid - 1一定不能写成left mid。否则当mid位置不等于target时区间没有真正缩小可能死循环。如果用标准库也可以写成import bisect def searchMatrix_bisect(matrix, target): for row in matrix: pos bisect.bisect_left(row, target) if pos len(row) and row[pos] target: return True return Falsebisect_left返回第一个大于等于target的位置。如果这个位置不越界并且值等于target就说明找到了。这个写法代码更少但仍然建议先理解手写版本。3.4 本地运行环境与力扣提交的差异很多新手会在本地IDE里跑得好好的一提交到力扣就报错原因往往不是算法而是环境差异。第一力扣要求你提交的类名是Solution入口函数名是题目标配的searchMatrix。你在本地测试时可以把函数改成searchMatrix_z之类的名字但提交版本必须保留标准签名。第二力扣在线环境已经预装了Python标准库但不要依赖第三方库比如numpy。我看到热门搜索词里有“python安装numpy库”的疑问这在数据分析项目里是常规操作但在算法题提交里反而容易出问题。如果本地想用numpy生成随机矩阵来测试那是可以的但最终提交版本必须只使用标准库。第三如果你在本地命令行刷题Windows上安装Python时一定要勾选“Add Python to PATH”否则在cmd里输入python会提示找不到命令。VSCode里装好Python插件后左下角状态栏会显示当前解释器点一下就能切换。调试时直接在代码行号左边打红点按F5就可以进入调试模式在Watch窗口里看row和col的变化比print方便很多。4. 常见问题与排查手册4.1 提交后报IndexError怎么办先看错误信息里的下标越界常见的根源有三个。第一个是矩阵为空。解决办法就是开头的if not matrix or not matrix[0]。第二个是行列索引写反用了matrix[col][row]。这个错误在非方阵里特别明显比如一个5行3列的矩阵col最大可能是4matrix[4][...]可能越界。记住Python二维列表的读取顺序是matrix[行索引][列索引]。第三个是Z扫描里循环条件写错。比如把while row rows and col 0写成while row rows and col 0当row等于rows时matrix[row]就越界了。因为合法行号是0到rows-1所以必须是row rows。4.2 明明有target却返回False这类问题最容易出现在方向写反的情况。看一个典型错误写法while row rows and col 0: cur matrix[row][col] if cur target: row 1 # 错当前值大应该往左 elif cur target: col - 1 # 错当前值小应该往下这种写法会让搜索路径变得非常奇怪最后大概率找不到正确答案。排查方法很简单在循环里打印每一步的row、col和cur对照矩阵手写模拟一遍看移动方向是不是“大于往左、小于往下”。如果方向反了改回来就好。另一个常见原因是有些人会尝试从左上角开始搜索。左上角是矩阵最小值如果target比它大向右和向下都更大你没法判断该走哪条路只能盲目遍历最终漏掉结果。这也是为什么必须从右上角或左下角开始。4.3 为什么右上角走Z字不会漏很多人担心如果target在左下角我从右上角开始一路向下向左是不是可能错过不会。关键在于每一轮比较都排除了一个完整方向。当前元素大于target时因为列的方向是递增的当前列往下所有元素都大于当前元素也就都大于target所以整列都可以丢。当前元素小于target时因为行的方向是递增的当前行往左所有元素都小于当前元素也就都小于target所以整行都可以丢。想象矩阵是一个搜索矩形边界从右上角开始不断向内收缩。向左移动相当于把矩形的右边界左移向下移动相当于把矩形的上边界下移。只要target在矩阵里它所在的区间就一定会被扫描到如果扫描结束还没找到说明它不在矩阵中。4.4 新手友好的调试小技巧我在日常刷题时常用几个简单的调试手段。第一个是assert自测。本地写几个已知用例assert searchMatrix_z([[1, 4, 7], [2, 5, 8], [3, 6, 9]], 5) is True assert searchMatrix_z([[1, 4, 7], [2, 5, 8], [3, 6, 9]], 10) is False assert searchMatrix_z([[]], 1) is False如果assert过不去说明实现有bug。第二个是打印搜索轨迹。很多在线IDE不支持断点print是最直接的。打印的时候不要只打value要连行列一起打方便定位。第三个是控制变量法。如果优化解法有问题先跑一遍暴力解法做对拍。用Python标准库random生成随机小矩阵然后比较两种解法结果是否一致。这一步能筛掉大量逻辑错误。症状可能原因解决方式IndexError没有处理matrix[]或[[]]加if not matrix or not matrix[0]IndexError行列索引写反检查matrix[row][col]IndexErrorwhile条件用了改为row rowscol 0超时用了暴力遍历改为逐行二分或Z扫描返回False但结果应该是True从左上角开始改为从右上角或左下角开始返回False但结果应该是True大于/小于分支方向写反打印轨迹手写模拟5. 从这题延伸出去的经验5.1 一题多解到底在锻炼什么搜索二维矩阵II是少有的能同时练到暴力、二分、线性扫描三种思维的题。你从暴力到逐行二分再到Z扫描每一步都在做同一件事更充分地利用题目给出的有序条件。暴力完全不用有序条件逐行二分用了“每行有序”但没用“每列有序”Z扫描把两个条件都用上了。这个思维递进比记住一个解法更重要。面试里如果被问到这题我建议按这个顺序回答先说暴力O(mn)再说逐行二分O(mlog n)最后给出右上角扫描O(mn)。每一层都说清楚优化点在哪面试官会觉得你不是背题而是真的理解。5.2 把一道题变成一组题力扣里至少有三道题和这道题强相关。LeetCode 74的“搜索二维矩阵”它的矩阵是每行开头比上一行末尾大整体可以拍平成一个递增序列所以只需要一次二分。LeetCode 240就是这题行列各自递增但整体不递增解法升级成了Z扫描。还有“搜索旋转排序数组”系列也是二分思想的变化。如果你刷完这题还有余力建议把LeetCode 74和240放在一起对比总结重点想清楚“为什么74能拍平240不能”。很多面试官喜欢先出74再追问如果你改变矩阵结构怎么处理其实就是想考你240的解法。5.3 面试时怎么讲这题才加分我有一次模拟面试练过这题经验是先画图再讲思路最后再写代码。画图不只是画矩阵而是把右上角这个“决策点”标出来然后演示一次“大于向左、小于向下”的路径让面试官直观看到每次排除一行或一列。讲复杂度时一定要直接说“最坏情况下row移动m次col移动n次所以是O(mn)”而不是笼统地说“线性的”。空间复杂度是O(1)因为只用几个临时变量。如果你能顺带提一句“如果矩阵行列长度差异很大也可以选从行数、列数中更适合的一侧开始”面试官通常会感到很惊喜。这代表你不仅会写代码还会根据输入规模调整策略。最后再分享一个自己的习惯刷hot100的题时我喜欢把每道题的“关键观察”用一句话写在题目前面。搜索二维矩阵II这句话就是“右上角是决策点向左变小向下变大”。等刷到类似的二维搜索题时我第一时间就会想到这个模式很快就能找到切口。这种从单题提炼成套路的方式比反复刷十道类似题都管用。希望这个思路也能帮到你。