最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

Problem 3:二维数组中的查找

XAMPP案例 admin 645浏览 0评论

一、题目描述
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

二、思路分析
首先分析该数组的特点,在向下和向右方向上,数值会递增。以二维数组中任意位置元素为例,同行右侧元素皆大于该点,同列下侧元素皆大于该点,因此该点右下侧元素皆大于该点。

clipboard.png

而右上侧和左下侧点都可能有大于该点的点,初步可认为,大于该值的点位于右侧和下侧。
因此,我们可以根据该数组的特点进行逐行剔除,达到缩小范围,查找目标值的目的。

算法思路
首先确定初始点,由于剔除某行/列,需要与目标值对比。初始点大于目标值,需要往小侧移动;初始点小于目标值,需要往大侧移动。而四个顶点,只有左下角和右下角,进行横向和纵向移动能高效筛选和剔除行列。

选择右上角为初始点,执行下述操作
1)如果该点等于目标值,结束查找
2)如果该点小于目标值,往大侧移动,下移一行(列索引不变)
3)如果该点大于目标值,往小侧移动,左移一列(行索引不变)
重复上述过程,直到索引超过数组边界。如果符合1,退出重复。这里,我们认为本题找到目标值即可,无需查找是否有其他位置的目标值。

根据上述思路,通过向左下移动,达到整行或者整列的剔除,实现比较快速的查找。可以把这个过程理解为剥洋葱,一层层剥开外层的非目标层,查找内部的目标值。

三、Java实现
源程序:

package jz_offer;

public class problem03
{
/**
* -查找二维数据arr中是否存在数值num
* @param arr:二维数组
* num:目标值
* @return 在二维数组中是否找到了目标值怒骂,返回类型boolean
*/
public static boolean findNum(int[][] arr,int num){
boolean flag=false; //标志位,为true时表示找到目标值
int i=0;
int j=arr[0].length-1;
while(flag!=true&&i<arr.length&&j>=0){
if(arr[i][j]==num){
flag = true;
break;
}else if(arr[i][j]<num){
i++;
}else{
j–;
}
}
return flag;
}
public static void main(String[] args){
int[][] array={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
boolean found=findNum(array,7);
System.out.println(“if the num 7 is in the array?”+found);
}
}

转载请注明:XAMPP中文组官网 » Problem 3:二维数组中的查找

您必须 登录 才能发表评论!