04 二维有序数组的查找
2018-11-20 03:15:12来源：博客园 阅读 ()
题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路：
#第一步：要判断数组是否非空，空数组 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 }
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：学生选题信息管理系统
- PC微信获取登录二维码 2020-05-18
- 前缀和 2020-05-04
- 二叉排序树 2020-05-02
- 纯虚函数与基类指针数组的运用 代码参考 2020-04-30
- STL之deque 2020-04-29
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
