欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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)
相关标签: 数据结构与算法