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

解题思路：

#第一步：要判断数组是否非空，空数组 return false，不用进行其他操作。

1）从数组的左下角或右上角遍历。时间：11ms，占用内存：1512k。复杂度：。

2）对每一行进行二分查找，通过遍历每一行得到答案。时间：，占用内存：，复杂度：nlogn。

3）

测试用例：

 1) 1,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]] true

方法一code:

//从左下角开始遍历
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
         if (array.empty())
             return false;
        
         int rows = array.size();
         int cols = array[0].size();
         for (int r=rows-1, c=0;r>=0&&c<cols;){
             if (target==array[r][c])
                 return true;
             else if (target>array[r][c])
                 c+=1;
             else
                 r-=1;
         }
         return false;
    }
};

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

方法二code:

方法三code:

 

编写代码时遇到的错误：

1）for (int r=rows,int c=0;r>=0&&c<cols;){ body ... }   //error

修正：int r=rows, c=0;

2）数组越界问题： 每行有cols个元素，角标范围是（0～cols-1），要减1。

3) 定义一个新的变量的时，要写类型。

基础知识：

1）int类型：/整除，向下取整。

2）二维vector初始化方法：

直接初始化：vector<vector<int> > arrayName (r, vector<int>(c, 0)); #r行c列

用resize()来控制大小：

vector<vector<int> > res;
        res.resize(r);//r行
        for (int k = 0; k < r; ++k){
            res[k].resize(c);//每行为c列
        }