【剑指offer - C++/Java】1、二维数组中的查找
发布日期:2021-07-01 00:05:05
浏览次数:2
分类:技术文章
本文共 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月14日 07时35分05秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01
未来已至,5G加持下的云游戏将走向何方?
2019-05-01
计算机网络 —— 网络层 1.
2019-05-01
Android生命周期
2019-05-01
Android 之 ContentProvider 与 ContentResolver
2019-05-01
【接口自动化】
2019-05-01
Spring Boot 安全框架 Shiro 入门
2019-05-01
如何用一句话激怒互联网人?
2019-05-01
用 Python 爬了点你们喜欢的电影
2019-05-01
推荐一位川大零基础转行 Python 的人生勇士
2019-05-01
讲真,做Python一定不要只会一个方向!
2019-05-01
Python解惑之:True与False
2019-05-01
你要的微信小程序终于来了
2019-05-01
有了这些 Chrome 插件,效率提升10倍(建议收藏)
2019-05-01
Python 开发者都会遇到的错误:UnboundLocalError
2019-05-01
只有1%的程序员搞懂过浮点数陷阱
2019-05-01
一名 Google 工程师的大数据处理经验
2019-05-01
命名难,难于上青天
2019-05-01
史上最烂项目:苦撑12年,600多万行代码...
2019-05-01