04 二维有序数组的查找

2018-11-20 03:15:12来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

解题思路:

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

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:学生选题信息管理系统

下一篇:书上关于*(p++)表达式的几种变形形式的思考题