题解 | #二维数组中的查找#
代码 1.0 错误
思路：
1、数组看作一个矩形区间 区间分成四块
2、 target与当前区间第一行的中间元素x比较大小
target>x时，target在当前区间的右半边；
target<x时，target在当前区间的左半边；
2、 target与当前区间第一列的中间元素y比较大小
target>y时，target在当前区间的下半边；
target<y时，target在当前区间的上半边；
3、查找范围缩小为原区间的四分之一
4、重复上述步骤
5、不知哪里有逻辑上的错误
package Find_and_sort;
//版本 1.0 （没有写完）
public class Find_ {
public static void main(String[] args) {
Solution_Find solution_find = new Solution_Find();
int target=16;
int [][] array=new int[][]{{1,2,3,4},{5,7,9,11},{6,8,16,17}};
boolean res=solution_find.Find(target,array);
System.out.println(res);
}
}
class Solution_Find {
public boolean Find(int target, int [][] array) {
//返回结果 空数组情况
if (array.length==0){
return false;
}
int res[]=new int[9];
int lengh_x=array.length;
int length_y=array[0].length;
//返回结果 越界<min or >max
int x=lengh_x/2;
int y=length_y/2;
int head_x=0;
int tail_x=array.length-1;
int head_y=0;
int tail_y=array[0].length-1;
while (res[0]!=-1001){
res=fenqu(target,array,x,lengh_x,head_x,tail_x,y,length_y,head_y,tail_y);
//int res[]=new int[]{0flage,1x,2length_x,3head_x,4tail_x,5y,6length_y,7head_y,8tail_y};
//更新分区数据
x=res[1];lengh_x=res[2];head_x=res[3];tail_x=res[4];
y=res[5];length_y=res[6];head_y=res[7];tail_y=res[8];
//找到了 直接退出循环 res[0]=-1001
//这次没找到 继续找 res[0]=-2001
//根本找不到 退出 res[0]=-3001
if (res[0]==-3001){
break;
}
}
//返回最终结果
if (res[0]==-1001){
return true;
}
else{
return false;
}
}
public int [] fenqu(int target,int [][] array,int x,int length_x,int head_x,int tail_x,int y,int length_y,int head_y,int tail_y){
// 1、将二位数组分成四个区
// 2、确定target所在区域
// 3、返回所在区域的数据:
// x length_x x方向的取值范围{head_x,tail_x},
// y length_y y方向的取值范围{head_y,tail_y}
//int res[]=new int[8];
//设置一个标记 flage 一般情况：找到目标返回-1001,未找到目标返回-2001(暂未找到 继续找)
// 特殊情况：找到目标返回-1001,未找到目标返回-3001(说明目标不在该数组中)
int flage=-2001;
//特殊情况的分区 只剩一个元素
if (length_x==1&&length_y==1){
if (target==array[head_y][y]){
flage=-1001;
}
else{
flage=-3001;
System.out.println("target不在该数组中");
}
}
//一般情况的分区
else{
//左右分区 y方向(横)
if (target==array[head_y][y]){
flage=-1001;
System.out.println("在当前分区y方向的中点处找到target");
}//
if (target<array[head_y][y]){//左分区
//y已知
length_y=length_y/2;//分区长度
//y方向的取值范围
head_y=y-length_y;
tail_y=y-1;
y=length_y/2;//新分区 y方向的中点
}
if (target>array[head_y][y]){//右分区
length_y=length_y-(length_y/2);//分区长度
//y方向的取值范围
head_y=y;
tail_x=y+length_y-1;
y=length_y/2;//新分区 y方向的中点
}
//上下分区 x方向(纵)
if (target==array[x][head_x]){
flage=-1001;
System.out.println("在当前分区x方向的中点处找到target");
}
if (target<array[x][head_x]){//上分区
//x已知
length_x=length_x/2;//分区长度
//x方向的取值范围
head_x=x-length_x;
tail_x=x-1;
x=length_x/2;//新分区 x方向的中点
}
if (target>array[x][head_x]){
length_x=length_x-(length_x/2);//分区长度
//x方向的取值范围
head_x=x;
tail_x=x+length_x-1;
x=length_x/2;//新分区 x方向的中点
}
}
//返回结果
int res[]=new int[]{flage,x,length_x,head_x,tail_x,y,length_y,head_y,tail_y};
return res;
}
}
代码 2.0 正确
思路：
target与左下角元素p(x,y)比较
target>p时 x不变 y+1；
target<p时 x-1 y不变；
|
|
|
class Solution_Find {
public boolean Find(int target, int [][] array){
//特殊情况
//判断二维数组为空！！！
if ((array==null||array.length==0)||(array.length==1&&array[0].length==0)){
return false;
}
else{
int x= array.length-1;
int y=0;
//一般情况
while(true){
if (array[x][y]==target) {
return true;
}
if (array[x][y]<target){
y=y+1;
if (y==array[0].length){
return false;
}
}
if (array[x][y]>target){
x=x-1;
if (x<0){
return false;
}
}
}
}
}
}
巨人网络成长空间 50人发布
