74. 搜索二维矩阵视频搜索二维矩阵 | LeetCode 74_哔哩哔哩_bilibili题目给定一个m×n的整数矩阵它有两个特殊性质1每一行都是从小到大排序的2每一行的第一个元素都大于上一行的最后一个元素。现在给你一个目标值要判断这个值是否存在于矩阵中。要求时间复杂度为O(log(m×n))思路及代码思路1逐行二分因为每一行都是有序的所以可以逐行二分class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: # 逐行进行二分查找 for row in matrix: left, right 0, len(row) - 1 while left right: mid (left right) // 2 if row[mid] target: return True elif row[mid] target: left mid 1 else: right mid - 1 return False时间复杂度为 m*log(n)不符合题目要求这种解法没有利用第二个性质即行与行之间也是有序的整个矩阵其实是全局有序思路2行级行内二分先用二分查找确定目标值在哪一行然后再在那一行内部进行二分查找第一步对行进行二分检查目标值是否落在当前行的范围内。如果当前行的第一个元素 目标值就网上找否则往下找第二步定位到行之后再在这一行内进行标准的二分查找class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: m, n len(matrix), len(matrix[0]) # 首先二分查找定位目标行 top, bottom 0, m-1 while top bottom: mid (top bottom) // 2 # 如果目标值在这一行的范围内 if matrix[mid][0] target matrix[mid][n-1]: break elif matrix[mid][0] target: bottom mid - 1 else: top mid 1 # 没有找到合适的行 if top bottom: return False # 目标值在行mid中 row mid # 开始在目标行内进行二分查找 left, right 0, n-1 while left right: mid (left right) // 2 if matrix[row][mid] target: return True elif matrix[row][mid] target: left mid 1 else: right mid - 1 return False时间复杂度为 O(log(m) log(n))等价于 O(log(m×n))符合题目要求思路3整体二分因为整个矩阵行内有序行间也有序可以把这个二维矩阵想象成一个一维的有序数组定义一个映射关系对于一维索引用整除列数得到行号用取余列数得到列号即一维索引 index — 二维行号 index // n二维列号 index % n有了这个映射就可以直接对整个矩阵进行一次二分查找class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: m, n len(matrix), len(matrix[0]) left, right 0, m * n - 1 # 搜索范围从 0 ~ 元素总数-1 while left right: mid (left right) // 2 # 一维索引映射为二维索引的行和列 row mid // n col mid % n if matrix[row][col] target: return True elif matrix[row][col] target: left mid 1 else: right mid - 1 return False时间复杂度为 O(log(m×n))空间复杂度是常数级别 O(1)