74. 搜索二维矩阵
https://leetcode-cn.com/problems/search-a-2d-matrix/
解法一:
通过坐标变换,将二维矩阵视为一维。由于是有序的,因此一维上依然是有序的。
n * m matrix convert to an array => matrix[x][y] => a[x * m + y]
an array convert to n * m matrix => a[x] =>matrix[x / m][x % m]
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
n = len(matrix)
if n == 0: #排除边界情况
return False
m = len(matrix[0])
if m == 0:
return False
l, h = 0, m * n - 1 #左右起点
#二分
while l <= h:
mid = (l + h) // 2 #中点
if matrix[mid // m][mid % m] < target:
l = mid + 1
elif matrix[mid // m][mid % m] > target:
h = mid - 1
else: #mid找到
break
return matrix[mid // m][mid % m] == target
最后更新于