04二维有序数组的查找

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

解题思路：

#第一步：要判断数组是否非空，空数组 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

 2）二维数组中不包含查找的数字（该查找数字小于最小值、大于最大值、介于中间值）

 3 ）传入空数组

 

方法一code:

 1 //从左下角开始遍历
 2 class solution {
 3 public:
 4     bool find(int target, vector<vector<int> > array) {
 5          if (array.empty())
 6              return false;
 7         
 8          int rows = array.size();
 9          int cols = array[0].size();
10          for (int r=rows-1, c=0;r>=0&&c<cols;){
11              if (target==array[r][c])
12                  return true;
13              else if (target>array[r][c])
14                  c+=1;
15              else
16                  r-=1;
17          }
18          return false;
19     }
20 };

code01

 1 class solution {
 2 public:
 3     bool find(int target, vector<vector<int> > array) {
 4          if (array.empty())
 5              return false;
 6         
 7          int rows = array.size()-1;
 8          int cols = 0;
 9          while (rows>=0 && cols<array[0].size()){
10              if (target==array[rows][cols])
11                  return true;
12              else if (target<array[rows][cols])
13                  rows-=1;
14              else
15                  cols+=1;
16          }
17          return false;
18     }
19 };

code01_02

方法二code:

code02

方法三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()来控制大小：

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