[LeetCode]剑指 Offer 04. 二维数组中的查找

算法标签 双指针

题目简叙

思路

线行查找的思路
一行从左到右递增
一列从上到下递增
那么我们依据性质 从第0行的最右侧开始就检查
如果目标值比这个值大，那么就到下一行
如果目标值比这个值小，那么久到前一个

代码

暴力

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0||matrix[0].size剑指 Offer 04. 二维数组中的查找剑指 Offer 04. 二维数组中的查找剑指 Offer 04. 二维数组中的查找()==0)return false;
        int n=matrix.size(),m=matrix[0].size();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(matrix[i][j]==target)
                    return true;
        return false;
    }
};

线行查找

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0||matrix[0].size()==0)return false;
        int n=matrix.size(),m=matrix[0].size();
        int x=0,y=m-1;
        while(x<n&&y>=0){
            if(matrix[x][y]==target)return true;
            if(matrix[x][y]>target)y--;
            else x++;
        }
        return false;
    }
};