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

74. 搜索二维矩阵

程序员文章站 2024-03-24 14:38:40
...

74. 搜索二维矩阵
74. 搜索二维矩阵

解1 二分搜索

两次二分搜索

  • 在第一列二分搜索target
    • 退出循环后 matrix[r][0] < target; matrix[l][0] > target (如果都存在)
  • 在 matrix的r索引行 二分搜索target
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        
        first = list()
        
        m = len(matrix)
        n = len(matrix[0])
        
        for i in range(m):
            first.append(matrix[i][0])
            
        l = 0
        r = m - 1
        
        while l <= r:
            mid = (l + r) // 2
            
            if first[mid] == target:
                return True
            
            if first[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
           
        if r == -1:
            return False
        
        li = matrix[r]
        l = 0
        r = n - 1
        
        while l <= r:
            mid = (l + r) // 2
            
            if li[mid] == target:
                return True
            
            if li[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
                
        return False
      

一次二分搜索

把矩阵从左到右、从上到下连起来就是一个递增的数组,可以用二分搜索来查找。现在只要找出数组下标到矩阵的映射关系就可以了:i -> [i // n][i % n],其中i是数组中的下标,n是矩阵的宽。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        
        m, n = len(matrix), len(matrix[0])
        
        l = 0
        r = m * n - 1
        
        while l <= r:
            
            mid = (l + r) // 2
            
            if matrix[mid // n][mid % n] == target:
                return True
            
            if matrix[mid // n][mid % n] < target:
                l = mid + 1
                
            else:
                r = mid - 1
                
        return False

解2

剑指offer第4题
从 右上角 或 左下角 开始遍历

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        
        # 剑指offer 从 右上角 或 左下角 遍历
        
        m = len(matrix) - 1
        n = len(matrix[0]) - 1
        
        i = 0
        j = n
        
        while i <= m and j >= 0:
            
            if matrix[i][j] == target:
                return True
            
            if matrix[i][j] < target:
                i += 1
            else:
                j -= 1
                
        return False