[Lc]面试题04二维数组中的查找

题目

240题

题解

可以一行一行的二分查找，但是比较慢，也没有利用这道题矩阵的性质
确定起点很重要，由于这道题矩阵的特殊形式，我们可以将起点定在右上（或者左下），然后与target比较，target大了就到下（右）找，小了就到左（上）找

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

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        //初始点定到右上角（左下也可以），即一个方向变大，一个方向变小，一种变形的二分思想吧
        int i = 0, j = matrix[0].size()-1;
        while(i<matrix.size() && j>=0){//超出矩阵跳出
            if(matrix[i][j] == target) return true;//等于返回true
            else if(matrix[i][j] > target) j--;//大了向左
            else i++;//小了向下
        }
        return false;
    }
};