【剑指offer - C++/Java】1、二维数组中的查找
发布日期:2021-07-01 00:05:05
浏览次数:3
分类:技术文章
本文共 1929 字,大约阅读时间需要 6 分钟。
学习交流加
- 个人qq: 1126137994
- 个人微信: liu1126137994
- 学习交流资源分享qq群: 962535112
题目链接:
文章目录
题目描述:
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
解题思路
两种思路
方法1
把每一行看成有序递增的数组,利用二分查找,通过遍历每一行得到答案。时间复杂度是nlogn
java代码:
public class Solution { public boolean Find(int target,int [][] array) { for(int i=0;iarray[i][mid]) low=mid+1; else if(target
C++代码:
class Solution { public: bool Find(int target, vector> array) { if(array.size()<1)return false; int low,high,mid; int size=array.size(); int len=array[0].size(); for(int i=0;i array[i][mid])low=mid+1; else high=mid-1; } } return false; }};
方法2
利用二维数组由上到下,由左到右递增的规律,如下图:
那么选取右上角或者左下角的元素a[row][col]与target进行比较,当target小于元素a[row][col]时,那么target必定在元素a[row][col]所在行的左边,不可能在下面,因为下面的元素比a[row][col]大。即col–;
当target大于元素a[row][col]时,那么target必定在元素a[row][col]所在列的下边,不可能在左边,因为边面的元素比a[row][col]小。即row++;
java代码:
public class Solution { public boolean Find(int target, int [][] array) { if(array.length<1)return false; int row=0,col=array[0].length-1; while(row=0){ if(target == array[row][col])return true; else if(target>array[row][col])++row; else --col; } return false; }}
C++代码:
class Solution { public: bool Find(int target, vector> array) { if(array.size()<1)return false; int row=0,col=array[0].size()-1; while(row =0){ if(target==array[row][col])return true; else if(target>array[row][col]) ++row; else --col; } return false; }};
总结
方法一很简单,但是效率不高。方法二比较巧妙,利用了该题中数组的特性,实际上可以将方法二想象成二维空间的二分搜索。它还是一种二分法的应用。
学习探讨加:
qq:1126137994 微信:liu1126137994转载地址:https://lyy-0217.blog.csdn.net/article/details/83629631 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月18日 02时50分42秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
vs中动态DLL与静态LIB工程中加入版本信息的方法
2019-05-01
大数据分析技术与应用一站式学习(值得收藏)_v20200418
2019-05-01
Qt 在windows下的串口读写
2019-05-01
SpringApplication执行流程
2019-05-01
自定义Starter
2019-05-01
分布式事务原理探究(一)
2019-05-01
spring cloud consul 应用的多实例名的解决
2019-05-01
人工智能为什么这么火?看看安防江湖30年血战就知道了
2019-05-01
“前端智能为安防产生新的数据价值”
2019-05-01
高斯混合模型
2019-05-01
(8)CMake入门笔记--CMake语法
2019-05-01
3D点云图实验
2019-05-01
解析大端模式和小端模式
2019-05-01
define入门
2019-05-01
头文件中 #ifndef---#define---#endif的作用
2019-05-01
分析Linux内核启动过程:从start_kernel到init
2019-05-01
系统调用过程的理解
2019-05-01
Ant内置任务之whichresource
2019-05-01
Ant内置任务之symlink
2019-05-01
jface databinding:部分实现POJO对象的监测
2019-05-01