240. 搜索二维矩阵 II

image-20211025100921484

解题思路：

​ 这道题的关键是找到右上角作为起始点，这样的话整个矩阵就能看做是一个二叉搜索树。

  • 以n,m为行列，判断情况如下：
    • 如果target<matrix[n][m]，则取二叉搜索树中的左子树，即n–
    • 如果target>matrix[n][m]，则取二叉搜索树中的右子树，即m++
    • 如果target==matrix[n][m]，则直接返回true

以下为C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //从右上角开始二叉树搜索
        int n=0,row=matrix.size(),m=matrix[0].size()-1;
        while(n<row&&m>=0){
            if(target<matrix[n][m]){
                m--;
            }else if(target>matrix[n][m]){
                n++;
            }else{
                return true;
            }
        }
        return false;
    }
};