class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix) == 0:
return False
row = 0
col = len(matrix[0])-1
while row < len(matrix) and col >=0:
if(matrix[row][col] < target):
row=row+1
elif (matrix[row][col]>target):
col = col -1
else:
return True
return False
方法二
利用矩陣的遞增性質(zhì)
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix) == 0:
return False
m = len(matrix)
n = len(matrix[0])
low = 0
high = m*n-1
while low<=high:
mid = low + (high-low)/2
row = mid/n
col = mid%n
if(matrix[row][col]> target):
high = mid -1
elif(matrix[row][col]<target):
low = mid+1
else:
return True
return False
