Leetcode 240.搜索二维矩阵 II

题目描述：

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

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

示例 1：

1
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 = 5
输出：true

示例 2：

1
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^9 <= matix[i][j] <= 10^9$
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• $-10^9 <= target <= 10^9$

链接：

https://leetcode-cn.com/problems/search-a-2d-matrix-ii

题目分析

  因为矩阵是相对有序的，对于一个节点，若 target 比它小，则只能在左边或者上边；若 target 比它大，则只能在右边或者下边。这样搜索路径有两条不好选择。如果我们从左下角开始搜索，若 target 小则只能往上边搜索，若 target 大则只能往右边搜索，我们只规定两个合法的移动方向，由于严格的大小关系，若 target 存在是一定不会错过的。同理，从右上角往左下角搜索也是可以的。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i = matrix.size()-1;
        int j = 0;
        while(i >= 0 && j < matrix[0].size()){
            if(matrix[i][j] > target) i--;
            else if(matrix[i][j] < target) j++;
            else return true;
        }
        return false;
    }
};

  时间复杂度：$O(m+n)$，其中 $m、n$ 分别为二维矩阵的行数和列数。我们的搜索方向只有右和上，最多只能走过 $m+n-1$ 步到达右上角。
  空间复杂度：$O(1)$。我们只需要根据搜索得到的大小进行移动，只需要常数个变量的空间。

  PS：官方题解中还有二分法等高端操作，非常复杂，时间复杂度也没有比这个好，就没有进行学习，这种方法还是十分巧妙和简洁的。