LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】

题目描述：

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

解题思路一：先二分查找行，再二分查找列。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        up, down = 0, m - 1
        while up <= down:
            mid = up + (down - up) // 2
            if matrix[mid][0] < target:
                up = mid + 1
            elif matrix[mid][0] > target:
                down = mid - 1
            else:
                return True
        print(matrix[up-1], target)
        left, right = 0, n - 1
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[up-1][mid] < target:
                left = mid + 1
            elif matrix[up-1][mid] > target:
                right = mid - 1
            else:
                return True
        return False

# 同意
class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        col0 = [row[0] for row in matrix]
        target_row = bisect.bisect_right(col0, target) - 1
        if target_row < 0:
            return False
        target_col = bisect.bisect_left(matrix[target_row], target)
        if target_col >= N:
            return False
        if matrix[target_row][target_col] == target:
            return True
        return False

时间复杂度：O(logn + logm)
空间复杂度：O(1)

解题思路二：暴力遍历，也能过。

class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        for i in range(M):
            for j in range(N):
                if matrix[i][j] == target:
                    return True
        return False

时间复杂度：O(nm)
空间复杂度：O(1)

解题思路三：用python的in。

class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        for i in range(M):
            if target > matrix[i][N - 1]:
                continue
            if target in matrix[i]:
                return True
        return False

时间复杂度：O(logn + m)
空间复杂度：O(1)