Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example:
Consider the following 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]
]
Given target = 5, return true.
Given target = 20, return false.
这个题目思路, 1. brute force T: O(m*n) 2. T: O(m+n) 3. T: O(lg(n!)) 先找第一行, 第一列, 2n 再从(1,1) 开始扫第二行第二列, 2(n-1), .... 所以是lgn + lg (n-1) + lg(n-2)...lg(1) = lg(n!)
1) T: O(m*n)
两个for loop即可.
2) T: O(m + n)
#O(n + m) , O(1)
if not matrix or len(matrix[0]) == 0: return False
lr, lc = len(matrix), len(matrix[0])
r, c = lr - 1, 0
while r >= 0 and c < lc:
if matrix[r][c] > target:
r -= 1
elif matrix[r][c] < target:
c += 1
else:
return True
return False
3) T: O(lg(n!))
# T: O(lg(n!)) S: O(1)
def helper(i, flag):
l = i
r = lrc[0]-1 if flag == 'row' else lrc[1] -1if flag == 'col':
while l + 1 < r:
mid = l + (r - l)//2
if matrix[i][mid] > target:
r = mid
elif matrix[i][mid] < target:
l = mid
else:
return True
if target in [matrix[i][l], matrix[i][r]]:
return True
return False
else:
while l + 1 <r:
mid = l + (r - l)//2
if matrix[mid][i] > target:
r = mid
elif matrix[mid][i] < target:
l = mid
else:
return True
if target in [matrix[l][i], matrix[r][i]]:
return True
return False if not matrix or len(matrix[0]) == 0: return False
lrc = [len(matrix), len(matrix[0])]
for i in range(min(lrc)):
row_check = helper(i, "row")
col_check = helper(i, "col")
if row_check or col_check: return True
return False