二维数组中的查找——牛客剑指offer
题目描述:
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
输入参数:target(查找值) array(二维数组)
解题思路:
1、python代码
python实现比较简单,使用for in循环取出数组的每行i,然后使用in操作符判断target是否在行i中
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
for i in array:
if target in i:
return True
return False
2、java代码
我们先看一个符合题目要求的数组
数组特点:每行元素满足从左向右增大,每列元素满足自上而下增大
同行不同列的数值存在确定的大小关系,同列不同行的数值存在确定的大小关系,数值减小的方向为:向上或向左(数值增大的方向:向下或向右)
需要注意,不同行不同列的数据间并无确定的大小关系。例如:a[1][0]>a[0][0],但是a[1][0]<a[0][2]。
考虑到数组的最后一行每个元素均为所在列的最大值,如果其小于要搜索的值,那可以直接忽略该列及其之前列的所有元素。
算法(递归):
m:行数 n:列数
(1)遍历最后一行(rowindex=m-1),找到第一个大于target的元素,存储其列索引colindex
(2)向上搜索:find(rowindex,colindex,"up",target,array)
(2)递归
a.当前操作为向上搜索(direction='up'):
如果rowindex==0:已经搜索至第一行,无解,返回false
否则,rowindex-=1
b.当前操作为向右搜索(direction='right'):
如果colindex==n-1:已经搜索至最后一列,无解,返回false
否则,colindex+=1
a.如果array[rowindex][colindex]==target:返回true
b.如果array[rowindex][colindex]>target:向上搜索find(rowindex,colindex,"up",target,array)
c.如果array[rowindex][colindex]<target:向右搜索find(rowindex,colindex,"right",target,array)
按照如上算法和数组,举例说明,搜索元素12步骤如下:
(1)m=4,n=4.最后一行第一个大于12的元素为13,存储其行列索引,rowindex=3,colindex=2
(根据数值大小排列的特点,可以排除掉第一列和第二列的所有元素)
(2)向上搜索:find(rowindex=3,colindex=2,direction="up",target=11,array)
(3)递归:
向上搜索:rowindex=2,colindex=2,10<12:向右搜索
向右搜索:rowindex=2,colindex=3,13>12:向上搜索
向上搜索:rowindex=1,colindex=3,12=12:停止搜索,返回true
代码如下:
public class Solution {
public boolean Find(int target, int [][] array) {
int m=array.length;
int n=array[0].length;
int colindex=-1;
int rowindex=m-1;
for(int i=0;i<n;i++){
if(array[m-1][i]>target){
colindex=i;
break;
}
else if (array[m-1][i]==target){
return true;
}
}
if(colindex==-1){
return false;
}
else{
return find(rowindex,colindex,"up",target,array);
}
} public boolean find(int rowindex,int colindex,String direction,int target, int [][] array){
if(direction=="up"){
if(rowindex==0){
return false;
}
else{
rowindex--;
}
}
else if(direction=="right"){
if(colindex==array[0].length-1){
return false;
}
else{
colindex++;
}
}
if(array[rowindex][colindex]<target){
return find(rowindex,colindex,"right",target,array);
}
else if(array[rowindex][colindex]>target){
return find(rowindex,colindex,"up",target,array);
}
else{
return true;
}
}
//测试代码
// public static void main(String[]args){
// int array1[][]={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
// Solution sol=new Solution();
// boolean a=sol.Find(14,array1);
// System.out.println(a);
// }
}
最新文章
- hmm
- pdf预览-js版本
- redis清空缓存
- JAVA网络编程
- Unity3D入门之GUI基础以及常用GUI控件使用(2)
- 原子操作 Interlocked系列函数
- HTML5+CSS3+JQuery打造自定义视频播放器
- Memcached使用笔记
- CF380C Sereja and Brackets [想法+线段树]
- 4、第4次课 CSS代码第三节课20150923
- 实例讲解MySQL联合查询
- 伪静态规则写法RewriteRule-htaccess详细语法使用
- PHP代码,拒绝频繁访问
- URL传参中文乱码encodeURI、UrlDecode
- js调试模式控制台输出信息
- 【Android Developers Training】 78. 序言:执行网络操作
- Linux系列教程(九)——Linux常用命令之网络和关机重启命令
- 微信小程序教学第四章第一节(含视频):小程序中级实战教程:详情-页面制作
- 安装cocoa pods时出现Operation not permitted - /usr/bin/xcodeproj的问题
- mybatis框架(7)---mybatis逆向工程
热门文章
- HDU 5894 hannnnah_j’s Biological Test ——(组合数)
- 输出变量的界值(int、float、long.....)
- 用 Docker 搭建 ORACLE 数据库开发环境
- C++入门经典-例6.21-比较string字符串,比较两个字符串
- 20191114-3 Beta阶段贡献分配
- git下载fastadmin
- For 循环 kotlin(10)
- linux常用查看系统操作的linux命令
- System 源码阅读
- c# httphelper (苏飞老师)