"剑指Offer:二维数组中的查找(Java代码)"
题目要求编写一个函数,判断一个二维数组中是否包含某个整数。给定的二维数组是有序的,每一行从左到右递增,每一列从上到下递增。函数需要输出一个布尔值,true表示找到了目标整数,false表示没有找到。 首先我们可以观察到,从右上角开始查找是一个不错的策略。因为右上角的数是当前行的最大值,同时也是当前列的最小值。根据二维数组的有序性质,我们可以根据目标整数与右上角的数的大小比较,来决定下一步搜索的方向。 具体的算法可以如下: 1. 如果二维数组的行数或列数为0,那么直接返回false。 2. 初始化两个指针i和j,分别指向二维数组的右上角。 3. 进入一个循环,循环的条件是i小于二维数组的行数且j大于等于0: a. 如果目标整数与二维数组的右上角数相等,那么直接返回true,表示找到了目标整数。 b. 如果目标整数小于二维数组的右上角数,那么目标整数必然在当前数的左边列,所以j减小1。 c. 如果目标整数大于二维数组的右上角数,那么目标整数必然在当前数的下边行,所以i增加1。 4. 如果循环结束,还没有找到目标整数,那么返回false,表示未找到。 下面是使用Java语言实现的代码: ``` class Solution { public boolean find(int[][] array, int target) { int row = array.length; if (row == 0) { return false; } int col = array[0].length; if (col == 0) { return false; } int i = 0, j = col - 1; // 从右上角开始 while (i < row && j >= 0) { if (target == array[i][j]) { return true; } else if (target < array[i][j]) { j--; } else { i++; } } return false; // 未找到目标整数 } } ``` 这样,我们就实现了一个函数,可以判断一个二维数组中是否包含某个整数。我们通过从右上角开始查找,不断根据比较结果调整搜索方向,可以在时间复杂度为O(m+n)的情况下找到目标整数。其中m为二维数组的行数,n为二维数组的列数。 建议大家可以尝试在输入描述给定的二维数组和目标整数上进行调试,验证代码的正确性。
剩余77页未读,继续阅读
- 粉丝: 0
- 资源: 229
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
评论0