题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路：
#第一步：要判断数组是否非空，空数组 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:
- 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 }
经验首页