搜索二维矩阵 II | 秋招知识库

矩阵的四个角是最特殊的，左上角的值最小，右下角的值最大，另两个角的值居中。对于有序数据，从右上角或者左下角这种中间值开始，可以帮助我们排除不含答案的行列。

注：也可以从左下角开始，方法类似。

总结：利用 $matrix$ 行列有序的性质，我们可以用 $O (1)$ 的时间获取 $O (m)$ 或 $O (n)$ 的信息。相比之下， $O (m n)$ 的暴力查找（一个一个地找），每次花费 $O (1)$ 的时间，只获取了 $O (1)$ 的信息。

这就是为什么我们可以把 $O (m n)$ 的暴力查找优化成 $O (m + n)$ 。

Python 解法1C++ 解法1

python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1  # 从右上角开始
        while i < m and j >= 0:  # 还有剩余元素
            if matrix[i][j] == target:
                return True  # 找到 target
            if matrix[i][j] < target:
                i += 1  # 这一行剩余元素全部小于 target，排除
            else:
                j -= 1  # 这一列剩余元素全部大于 target，排除
        return False

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1; // 从右上角开始
        while (i < m && j >= 0) { // 还有剩余元素
            if (matrix[i][j] == target) {
                return true; // 找到 target
            }
            if (matrix[i][j] < target) {
                i++; // 这一行剩余元素全部小于 target，排除
            } else {
                j--; // 这一列剩余元素全部大于 target，排除
            }
        }
        return false;
    }
};

复杂度分析

时间复杂度： $O (m + n)$ ，其中 $m$ 和 $n$ 分别为 $matrix$ 的行数和列数。每次循环排除掉一行或者一列，一共 $m + n$ 行列，最坏情况下需要排除 $m + n - 1$ 行列才能找到答案。
空间复杂度： $O (1)$ 。

注

如果你想出了一个“更快”的二分做法，试试下面这个数据：

Python 解法3C++ 解法3

python

n = 300
matrix = [[1] * (n - 1 - i) + [9] * (i + 1) for i in range(n)]
target = 5

cpp

// C++ 版待补充

二分做法在这个数据上的时间复杂度为 $O (n \log n)$ ，甚至更慢了。

相似题目

推荐完成 1351. 统计有序矩阵中的负数，加深对排除法的理解。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

复杂度分析 ​

注 ​

相似题目 ​

分类题单 ​

复杂度分析

注

相似题目

分类题单