【力扣-240. 搜索二维矩阵2 ✨】Python笔记

从暴力解法到线性查找LeetCode 240 题解摘要本文深入剖析 LeetCode 240 题「搜索二维矩阵 II」。面对行与列均有序的矩阵不能简单套用二分查找而应利用其特性从右上角开始线性查找将时间复杂度优化至 O(mn)。 核心知识点有序矩阵的特性与Z 字形查找在解决这道题之前需要理解二维矩阵中行有序和列有序意味着什么以及如何利用这个特性。二分查找的局限性对于普通的有序数组习惯使用二分查找。但在二维矩阵中如果直接对每一行进行二分查找时间复杂度是 $O(m \log n)$。问题这虽然可行但没有充分利用列也是有序这一条件。为什么从右上角开始这是本题最精妙的思路。选择从矩阵的右上角或者左下角作为起点可以将矩阵看作一棵二叉搜索树当前元素目标值由于该行右边的数都比当前数大该行无解只能向下走寻找更大的数。当前元素目标值由于该列下方的数都比当前数大该列无解只能向左走寻找更小的数。当前元素目标值找到答案返回True。这种策略每一步都能排除一行或一列最终形成一个类似Z字形的搜索路径时间复杂度仅为 $O(mn)$。 题目解析LeetCode 240. 搜索二维矩阵 II题目描述每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例输入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 代码实现Python根据上述思路从右上角开始遍历利用指针模拟向下和向左的移动。from typing import List class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: if not matrix or not matrix[0]: return False # 初始化指针在右上角 # row: 行索引col: 列索引 row, col 0, len(matrix[0]) - 1 # 当指针在矩阵范围内时循环 while row len(matrix) and col 0: if matrix[row][col] target: return True elif matrix[row][col] target: # 当前数大于目标向左走缩小列 col - 1 else: # 当前数小于目标向下走增大行 row 1 # 遍历结束未找到 return False 复杂度分析维度分析结果说明时间复杂度O(mn)最坏情况下指针需要从右上角走到左下角遍历mn个元素。空间复杂度O(1)只使用了常数级别的额外空间row, col 指针。 总结这道题是经典的算法思维题。关键在于打破常规不要试图把二维问题强行降维成一维去套用二分查找。利用矩阵的有序性通过选取合适的起点右上角或左下角可以将查找过程转化为线性时间复杂度的高效操作。