leetcode 搜索二维矩阵 II python3
程序员文章站
2022-07-14 15:12:29
...
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 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]
]
给定 target = 5,返回 true。
给定 target = 20,返回 false。
二分法搜索
矩阵已经排过序,就需要使用二分法搜索以加快我们的算法。
算法:
首先,我们确保矩阵不为空。那么,如果我们迭代矩阵对角线,从当前元素对列和行搜索,我们可以保持从当前 (row,col)(row,col) 对开始的行和列为已排序。 因此,我们总是可以二分搜索这些行和列切片。我们以如下逻辑的方式进行 : 在对角线上迭代,二分搜索行和列,直到对角线的迭代元素用完为止(意味着我们可以返回 false )或者找到目标(意味着我们可以返回 true )。binary search 函数的工作原理和普通的二分搜索一样,但需要同时搜索二维数组的行和列。
class Solution:
def binary_search(self, matrix, target, start, vertical):
lo = start
hi = len(matrix[0])-1 if vertical else len(matrix)-1
while hi >= lo:
mid = (lo + hi)//2
if vertical: # searching a column
if matrix[start][mid] < target:
lo = mid + 1
elif matrix[start][mid] > target:
hi = mid - 1
else:
return True
else: # searching a row
if matrix[mid][start] < target:
lo = mid + 1
elif matrix[mid][start] > target:
hi = mid - 1
else:
return True
return False
def searchMatrix(self, matrix, target):
# an empty matrix obviously does not contain `target`
if not matrix:
return False
# iterate over matrix diagonals starting in bottom left.
for i in range(min(len(matrix), len(matrix[0]))):
vertical_found = self.binary_search(matrix, target, i, True)
horizontal_found = self.binary_search(matrix, target, i, False)
if vertical_found or horizontal_found:
return True
return False
https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-2/
方法二:
'''
沿中间列从上向下搜索,直至元素大于目标值(或许碰不到,那就搜索到底),以该元素为中心,递归搜索其左下和右上矩阵,直至找到相等值。
严格注意,递归的三大条件:
(1)有基本结束条件;
(2)缩小规模,走向基本结束条件;
(3)调用自身。
'''
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix:
return False
def search_rec(left,up,right,down):
if left>right or up>down:
return False
elif target<matrix[up][left] or target>matrix[down][right]:
return False
mid=left+(right-left)//2
row=up
while row<=down and matrix[row][mid]<=target:
if matrix[row][mid]==target:
return True
row+=1
return search_rec(left,row,mid-1,down) or search_rec(mid+1,up,right,row-1)
return search_rec(0,0,len(matrix[0])-1,len(matrix)-1)