c/c++语言开发共享04二维有序数组的查找

题目:在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 解题思路: #第一步:要判断数组是否非空,空数组 return false,不用进行其他操作。 1) …

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

解题思路:

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

04二维有序数组的查找

 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

04二维有序数组的查找

 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:

04二维有序数组的查找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         }

 

www.ctvol.com true Article c/c++语言开发共享04二维有序数组的查找

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/606293.html

(0)
上一篇 2021年5月13日 下午9:02
下一篇 2021年5月13日 下午9:05

精彩推荐