题意分析

  • 给我们一个二维数组，这个二维数组从上到下，从左到右都是递增的，需要我们判断这个二维数组中是否存在一个给定的数字。如果存在，那么直接返回true，否则返回false

思路分析

思路一 暴力法

  • 我们可以对这个二维数组直接进行遍历，然后我们逐个进行判断是否存在，如果存在直接返回true，最后遍历完整个数组都没有退出，那么直接返回false。

  • 代码如下

    • 需要对二维数组的每个元素进行遍历，时间复杂度为O(n^2)
    • 存储一个二维数组，空间复杂度为O(n^2) 
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        // 利用C++的auto进行遍历
        for(auto x:array) {
            for(auto y:x){
                // 如果存在，直接返回true
                if(y==target){
                    return true;
                }
            }
        }
        return false;
    }
};

思路二 双指针移动法

  • 如果这个是一个没有任何规律的数组，那么可能就只有那种写法了，但是这个题目告诉我们这个数字从上到下，从左到右都是递增的，所以我们可以从这个方向入手。我们发现，我们找一个数，最快的办法无非就是利用二分进行查找，但是我们发现这个题目是一个二维单调的。所以我们要想办法找到一个方法可以在我们判断到数字小了或者大了的时候可以进行一个范围的缩小。这样的话，我们就可以定义两个指针，放到右上角或者左下角。这里我放到右上角进行讨论。
    初始的时候，我们的两个x和y的指针放到了右上角。这样的话我们可以与目标数进行比较，如果发现这个数比目标数小了，我们就把y指针往下进行移动，y指针自增。如果发现这个数比目标数大了，我们就可以往左边方向进行移动，x指针自减。
  • 可以结合下面的图进行理解。

图片说明

  • 代码如下，由于x和y分别只能往一个方向进行移动
    • 右上角版,最有最多只会遍历一行和一列的长度，时间复杂度为O(n+m)
    • 二维数组存储所有的元素，空间的复杂度为O(n^2) 
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int len1=array.size();  // 计算行数
        int len2=array[0].size();  //计算列数
        int posx=0,posy=len2-1; //定义两个指针，分别指向x和y的坐标
        while(posx<len1&&posy>=0){
            // 当前的数字比目标数字大，x指针左移
            if(array[posx][posy]>target){
                posy--;
            // 当前的数字比目标数字小，y指针往下移动
            }else if(array[posx][posy]<target){
               posx++;
            }else{
                return true;
            }
        }
        return false;
    }
};
  • 左下角版
    • 从左下角开始遍历，最多遍历一行和一列的长度，时间复杂度为O(n+m)
    • 需要用长度为n的二维数组存储所有的元素，空间复杂度为O(n^2) 
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int len1=array.size(); // 行数
        int len2=array[0].size();  //列数
        int posx=len1-1,posy=0; // 定义两个指针，分别表示x和y的指针
        while(posx>=0&&posy<len2){
            // 当前的数字比目标数字大，x指针往上移动
            if(array[posx][posy]>target){
                posx--;
            // 当前的数字比目标数字小，y指针往右方向移动
            }else if(array[posx][posy]<target){
               posy++;
            }else{
                return true;
            }
        }
        return false;
    }
};