240. 搜索二维矩阵 II

Problem: 240. 搜索二维矩阵 II

思路

最干脆的方法是分别遍历矩阵的每一行和每一列，时间复杂度为$O(n^2)$，空间复杂度为$O(1)$

由于行和列都是有序的，所以可以考虑二分查找，也可以分为两种方法

方法一：可以直接对行和列分别进行二分， 时间复杂度为$O(min(n,m)logn)$，空间复杂度为$O(1)$
方法二：可以先对对角线进行二分，然后再分别对行和列进行二分，时间复杂度为$O(min(n,m)logn)$，空间复杂度为$O(1)$，但是这个要比方法一优化一些

解题方法

二分查找

复杂度

时间复杂度: $O(min(n,m)logn)$

空间复杂度: $O(1)$

Code

class Solution:
    # 遍历行，行不变，变得是列
    def binary_search_row(self, matrix, target, begin, cols):
        l = begin
        r = cols
        while l < r:
            mid = l + r + 1 >> 1
            if matrix[begin][mid] <= target:
                l = mid
            else:
                r = mid - 1
        return begin<=l<=cols and matrix[begin][l] == target
        
    # 遍历列，列不变，行变
    def binary_search_col(self, matrix, target, begin, rows):
        l = begin
        r = rows
        while l < r:
            mid = l + r + 1 >> 1
            if matrix[mid][begin] <= target:
                l = mid
            else:
                r = mid - 1
        return begin<=l<=rows and matrix[l][begin] == target


    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 依次二分查找对角线、行和列
        m, n = len(matrix), len(matrix[0])
        # 遍历对角线
        min_val = min(m, n)
        l, r = 0, min_val - 1
        while l < r:
            mid = l + r + 1>> 1
            if matrix[mid][mid] <= target:
                l = mid
            else: 
                r = mid - 1
        if matrix[l][l] == target:
            return True
        
        for i in range(l + 1):
            if self.binary_search_row(matrix, target, i, n - 1) or self.binary_search_col(matrix, target, i, m - 1):
                return True
        return False