剑指Offer_题解 C++

1.二维数组中的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

 

C++版

 

思路，本来想着暴力写一遍，但是暴力估计面试的时候直接被pass，所以思考了优化，首先能确定这个二维数组的规模是一个矩形，也就是每个一维的长度都相等的二维数组。然后尝试先确定答案的所在行，然后确定答案的所在列。但是这是个错误思路。错误的原因是因为题目只分别保证了横向递增和纵向递增，不保证横纵同时递增，所以没法分别确定行和列。随后看了一下讨论区的思路，十分明确，

/* 思路

* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，

* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移

* 要查找数字比左下角数字小时，上移

*/

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
            if(array.size()==0){return false;}
             if(array[0].size()==0){return false;}
             int i = array[0].size()-1;
             int j = 0;
             bool flag = false;
             while(i>=0 && j<array.size()){
                if(array[j][i]==target){return true;}
                if(array[j][i]>target){i--;}
                else{j++;}
             }
             return flag;

    }
};

以上是我的代码，在调试的过程中写出了一万遍运行错误RE，最后只能手写了测试样例。

int main()
{
    vector<int>vp;
    vector<vector<int> >v;
    for(int i=0;i<5;i++){
        vp.push_back(i);
    }
    v.push_back(vp);
    vp.clear();
    for(int i=0;i<5;i++){
        vp.push_back(i+5);
    }

    v.push_back(vp);
    vp.clear();
    for(int i=0;i<5;i++){
        vp.push_back(i+10);
    }
    v.push_back(vp);


    Solution s;
    bool flag = s.Find(11,v);
    if(flag){
        cout<<"yes"<<endl;
    }else{
        cout<<"NO"<<endl;

    }

    return 0;
}

以上是测试样例代码，最后发现测试数据里存在空数据。所以

if(array.size()==0){return false;}

if(array[0].size()==0){return false;}
加上这两句话就过了。