题解 | #二维数组中的查找#

题目难度：中等
题目考察：尺取，枚举
题目描述
给你一个数字target和一个二维数组，查找二维数组内是否存在数字，存在返回true，不存在返回false。
题目链接
算法1（暴力枚举）：
题目要确定二维数组内是否存在某个值，简单的思路就是暴力枚举具体做法如下
定义一个bool变量flag，遍历二维数组，存在这个数字即将flag变为true，最后返回flag即可
代码如下：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int flag=0;
        for(int i=0;i<array.size();i++) 
            for(int j=0;j<array[i].size();j++)
                //枚举二维数组里的每一个数
                if(array[i][j]==target)
                 {
                    flag=1;
                    return flag; 
                    //找到相等的数返回1
                 }
            return false;
            //没找到返回0
}; 
}

遍历了二维数组，所以时间复杂度O(n^2)
没有额外空间，空间复杂度O(1)
但是没有用到题目中的性质，明显不是最优解，下面来进行优化
算法2（利用单调性双指针）：
二维数组是从左向右单调的，从上到下也是单调的，

上面每次移动都是因为二维数组是从左向右单调的，从上到下也是单调的，所以可以保证正确性，
因此时间复杂度就降为了O(行+列)
下面给出代码

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
         if(array.size()==0||array[0].size()==0) return false;
            //特判空数组返回false
        int x=array[0].size()-1;
        int y=0;
            //从右上角开始移动
        while (x>=0&&y<array.size()){
            if(target==array[y][x])  return true;
                //只要找到了就直接返回false
            if(target>array[y][x]) y++;
                //向下移动
            else x--;
            //当前行大于target,向左移动
        }
        return false;
        //没找到返回false
    }
};

时间复杂度O(行+列)
空间复杂度O(1)