74. Search a 2D Matrix
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 from left to right.
The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
第三类 Binary search ,在二维上运用。
二维二分查找,其实可以将二维的坐标 虚拟 转变为一维,就又变成了普通的二分查找
矩阵坐标转换,mid 不加一的原因:
mid = s + (e - s) // 2
r = mid // col
c = mid % col
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
# print(matrix[1][3])
row = len(matrix)
if row == 0:
return False
col = len(matrix[0])
if col == 0:
return False
s ,e = 0, row * col - 1
while s + 1 < e:
mid = s + (e - s) // 2
r = mid // col
c = mid % col
print(r,c)
if matrix[r][c] == target:
return True
elif matrix[r][c] < target:
s = mid + 1
else:
e = mid - 1
r_s = s // col
c_s = s % col
r_e = e // col
c_e = e % col
print (s,e)
if matrix[r_s][c_s] == target or matrix[r_e][c_e] == target:
return True
return False
请多多指教。
文章标题:74. Search a 2D Matrix
本文作者:顺强
发布时间:2020-04-13, 23:59:00
原始链接:http://shunqiang.ml/leetcode-74-search-a-2d-m/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。