LeetCode 74. Search a 2D Matrix 题解题目描述编写一个高效的算法来判断m x n矩阵中是否存在一个目标值。该矩阵具有如下特性每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。示例 1输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 3 输出true示例 2输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 13 输出false解题思路方法二分查找思路由于矩阵的每行都是升序排列且每行的第一个整数大于前一行的最后一个整数所以整个矩阵可以看作是一个一维的有序数组。我们可以使用二分查找来快速定位目标值。具体步骤计算矩阵的总元素个数total m * n。初始化左指针left为 0右指针right为total - 1。当left right时计算中间位置mid。将mid转换为二维坐标(row, col)其中row mid // ncol mid % n。比较matrix[row][col]与目标值的大小如果相等返回true。如果小于目标值将left设为mid 1。如果大于目标值将right设为mid - 1。如果循环结束仍未找到目标值返回false。复杂度分析时间复杂度O(log(m * n))其中 m 和 n 分别是矩阵的行数和列数。每次查找都会将查找区间减半。空间复杂度O(1)只需要常数级的额外空间。代码实现方法二分查找class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: # 处理边界情况 if not matrix or not matrix[0]: return False # 获取矩阵的行数和列数 m len(matrix) n len(matrix[0]) # 计算总元素个数 total m * n # 初始化左指针和右指针 left 0 right total - 1 # 当左指针小于等于右指针时继续查找 while left right: # 计算中间位置 mid left (right - left) // 2 # 将中间位置转换为二维坐标 row mid // n col mid % n # 获取中间元素 mid_val matrix[row][col] # 如果找到目标值返回 true if mid_val target: return True # 如果中间值小于目标值将左指针移到中间位置的右边 elif mid_val target: left mid 1 # 如果中间值大于目标值将右指针移到中间位置的左边 else: right mid - 1 # 如果没有找到目标值返回 false return False测试用例测试用例 1输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 3输出true测试用例 2输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 13输出false总结本题是二分查找的经典变体问题主要考察对二分查找算法的理解和应用。通过将二维矩阵看作一维有序数组我们可以使用二分查找来高效地定位目标值。二分查找的核心思想是使用两个指针分别指向查找区间的两端计算中间位置比较中间元素与目标值的大小根据比较结果缩小查找区间直到找到目标值或确定目标值不存在。这种方法的时间复杂度为 O(log(m * n))适用于大规模二维矩阵的查找。掌握二分查找的原理对于理解搜索算法和算法设计思想非常重要。