下水摸鱼溺水身亡,不疯魔不成活广播剧,森摩耶
题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路：
#第一步：要判断数组是否非空，空数组 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 };
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 };
方法二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 }
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论