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

题目描述：

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：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
示例 2：

输入：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 = 20
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10⁹ <= matrix[i][j] <= 10⁹
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10⁹ <= target <= 10⁹

解题思路一：从左下角或者右上角元素出发，来寻找target。

如下图所示，我们将矩阵逆时针旋转 45° ，并将其转化为图形式，发现其类似于 二叉搜索树 ，即对于每个元素，其左分支元素更小、右分支元素更大。因此，通过从 “根节点” 开始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目标值 target 。

“根节点” 对应的是矩阵的 “左下角” 和 “右上角” 元素，本文称之为 标志数 ，以 matrix 中的 左下角元素 为标志数 flag ，则有:

1. 若 flag > target ，则 target 一定在 flag 所在 行的上方 ，即 flag 所在行可被消去。
2. 若 flag < target ，则 target 一定在 flag 所在 列的右方 ，即 flag 所在列可被消去。

“右上角” 元素 也是类似

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        i, j = len(matrix) - 1, 0
        while i >= 0 and j < len(matrix[0]):
            if matrix[i][j] > target: 
                i -= 1
            elif matrix[i][j] < target:
                j += 1
            else:
                return True
        return False

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

解题思路二：右上角元素，代码

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        i, j = 0, len(matrix[0]) - 1
        while i < len(matrix) and j >= 0:
            if matrix[i][j] > target:
                j -= 1
            elif matrix[i][j] < target:
                i += 1
            else:
                return True
        return False

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

解题思路三：暴力也能过

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            for element in row:
                if element == target:
                    return True
        return False

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

解题思路四：二分查找

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            idx = bisect.bisect_left(row, target)
            if idx < len(row) and row[idx] == target:
                return True
        return False

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