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

题意分析

• 给你一个二维数组，这个二维数组从左到右是递增的，从上到下也是递增的。要我们判断某一个整数是否在这个数组里面。

思路分析

解法一 暴力解法

• 二维数组，判断是否存在某一个数字，似乎很好理解。最直接的方法就是直接暴力循环所有的位置，直接判断是否存在，这样的话最好的时间复杂度为O(1),最坏的时间复杂度为O(nm)

• 代码如下

  • 最坏的情况需要循环所有的位置，时间复杂度为O(nm),n为数组的行数，m为数组的列数
  • 这个题目如果不算题目的参数的空间的话，时间复杂度为O(1)

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        // 暴力循环每一个行
        for(auto x:array) {
            // 循环每一列
            for(auto y:x){
                // 判断这个数字是否是要找的数字
                if(y==target){
                    return true;
                }
            }
        }
        return false;
    }
};

解法二 思维查找

• 乍一看这个题目的时间复杂度似乎是不可以降了。如果是一个常规的当然是使用暴力了。但是其实我们没有用到题目中的这个数字行从上到下是递增的。列从左到右是递增的这两种情况。

• 看上面的图，我们可以发现，其实我么只需要选择右上角或者左下角进行移动即可。比如在右上角，因为行是从左到右递增的，列是从上到下递增的。对于右上角而言，我们发现这个位置的左边都是比它小的，下面都是比它大的，那么这不就是一个二分的很好的条件吗？所以我们以右上角（或者左下角)为起点，然后进行一个移动，我们不停判断这个位置的数字的相对大小进行移动。最后如果存在，就一定能找到。

• 代码如下

  • 看图，显然最坏的情况就是遍历一个行加一个列的长度，所以时间复杂度为O(n+m)
  • 基本没有使用额外的变量进行处理，空间复杂度为O(1)

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; // 以右下角为起始点
        while(posx>=0&&posy<len2){
            // 如果遇到这个数字大了，那么向上（小的地方)进行移动
            if(array[posx][posy]>target){
                posx--;
            // 如果遇到这个数字小了，那么向右（大的地方)进行移动
            }else if(array[posx][posy]<target){
               posy++;
            }else{
                return true;
            }
        }
        return false;
    }
};