leetcodeday74 –搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true
# [74] 搜索二维矩阵
#

# @lc code=start
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def twoserch(nums,i,j,target):
            # i=0
            # j=len(nums)-1
            if nums[0]==target:
                return True
            mid=(i+j)//2
            while i<j-1:
                mid=(i+j)//2
                if nums[mid]==target:
                    return True
                elif nums[mid]<target:
                    i=mid
                else:
                    j=mid
            return False


        j=-1
        for i in range(len(matrix)):
            if target<matrix[i][-1]:
                j=i
                break
            elif target==matrix[i][-1]:
                return True
        if j == -1:
            return False
        else:
            lens=len(matrix[j])
            return twoserch(matrix[j],0,lens-1,target)
# @lc code=end

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注