LintCode Q28 Search a 2D Matrix in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年12月10日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
"""
@param matrix, a list of lists of integers
@param target, an integer
@return a boolean, indicate whether matrix contains target
"""
def searchMatrix(self, matrix, target):
# write your code here
# binary search
# time complexity: O(log(m*n)) = O(log(m) + log(n))
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
m = len(matrix)
n = len(matrix[0])
lo = 0
hi = m * n - 1
while lo <= hi:
mi = lo + (hi - lo)/2
if matrix[mi/n][mi % n] < target: # row = mi/n, col = mi % n
lo = mi + 1
elif matrix[mi/n][mi % n] > target: # row = mi/n, col = mi % n
hi = mi - 1
else:
return True
return False
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。