题目描述

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

参考

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/

复杂度

时间：m*n ，m+n的解参见参考链接题解模块
空间：1

代码

class Solution {
public:
    /*
    * * * * * *
    * * * * * *
    * * * * * *
    * * * * * *
    
    */
    
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        if(m==0) return false;
        int n=matrix[0].size();
        if(n==0) return false;
        int rbe=0,cend=n-1;
        for(int i=0;i<m;i++){
            if(matrix[i][n-1]<target){
                continue;
            }else{
                rbe=i;
                break;
            }
        }
        // cout<<"rbe:"<<rbe<<endl;
        for(int i=rbe;i<m;i++){
            for(int j=0;j<=cend;j++){
                if(matrix[i][j]>target){
                    cend=j-1;
                }else if(matrix[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }
};