你的位置:首页 > Java教程

[Java教程]二维“有序”数组查找问题的解决


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

 
        例如下面的二维数组就是每行、没列都递增排序。如果在这个数组中查找数字7,则返回true(找得到);如果查找数字5,由于数组不含该数字,则返回false。
1289
24912
471013
681115


        如下图所示,会出现三种情况
  1. 数组中选取的数字(图中全黑的位置)刚好是要查找的数字(相等),查找过程结束;
  2. 选取的数字小于要查找的数字,那么根据数组排序的规则,要查找的数字应该在当前位置的右边或者下边(如下图2.1(a)所示)
  3. 选取的数字大于要查找的数字,那么要查找的数字应该在当前选取的位置的上边或者左边。

 

分析:
       由上图可知,当不等于要查找的数字的时候会出现两片要查找的区域重叠的情况。我们该怎么考虑呢?                 
        我们可以从数组的一个角上选取数字来和要查找的数字做比较,情况会变得简单一些。如:首先选取数组右上角的数字9。由于9大于7,并且还是第4列的第一个(也是最小的)的数字,因此7不可能出现在数字9所在的列。于是我们把这一列从需要考虑的区域内剔除,之后只需分析剩下的3列(如下图(a)所示)。在剩下的矩阵中,位于右上角的数字是8,同样8大于7,因此8所在的列我们也可以剔除。接下来我们只要分析剩下的两列即可(如下图(b) 所示)。
        在由剩下的两列组成的数组中,数字2位于数字的右上角。2小于7,那么要查找的7可能在2的右边,也有可能在2的下边。在前面的步骤中,我们已经发现2右边的列都已经被剔除了每页就是说7不可能出现在2的右边,因此7只有可能出现在2的下边。于是我们把数字2所在的行也剔除,值分析剩下的三行两列数组(如下图(c)所示)。在剩下的数字中4位于右上角,和前面一样,我们把数字4所在的行也剔除,最后剩下两行两列数字(如图(d)所示)
        在剩下的两行两列4个数字中,位于右上角的刚好就是我们要查找的数字7,于是查找过程就可以结束了。
 
1289
24912
471013
681115
(a)
1289
24912
471013
681115
(b)


1289
24912
471013
681115
(c)
1289
24912
471013
681115
(d)
    注:矩阵中加颜色的的区域是下一步查找的范围。


 
总结
        总结上述查找的过程,我们发现如下规律:首先选取数组中右上角的数字。如果该数字等于要查找的数字,查找过程结束;如果该数字大于要查找的数字,剔除这个数字所在;如果该数字小于要查找的数字,剔除这个数字所在的
 

编码实现
核心算法:
 /** *  * @param num 被查找的二维数组 * @param rows 行数 * @param columns 列数 * @param number 要查找的数字 * @return 是否找到要查找的数字(number) */ public static Boolean Find(int num[][],int rows,int columns,int number) { Boolean found = false; int row = 0; int column = columns - 1 ;  if( rows > 0 && columns >0) {  while(row < rows && column >= 0)  {  if(num[row][column] == number) //查找到  {   found = true;   break;  }  else if(num[row][column] >number)  {   --column; //删除列  }  else  {   ++row; //删除行  }    } } return found; }

 

 

 测试:

 

public static void main(String[] args) { //初始化数字的值 int num[][]= {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};  System.out.println(Find(num,4,4,7)); //在数组中  System.out.println(Find(num,4,4,5)); //5不在数组中 }

 

 

 结果:

truefalse

 





安徽旅游线路报价安徽旅游攻略大全安徽旅游路线推荐安徽自驾游攻略安徽旅游线路大全深圳清明节去哪玩?2015清明节深圳有什么好玩的地方? 礐石风景区几点开门?汕头礐石风景区游玩多长时间? 礐石风景区在哪里?汕头礐石风景区什么时候去最好? 礐石风景区有什么好吃的?汕头礐石风景区美食有哪些? 小鸟天堂景区春节门票多少钱?2015春节新会小鸟天堂门票价格? 2015小鸟天堂油菜花什么时间开?新会小鸟天堂景区油菜花开花时间? 2015春节小鸟天堂有什么好玩的?新会小鸟天堂景区春节活动介绍? 情人节将至 带着爱人去天津享受复古式“约泡” 田野绿世界要门票吗?佛冈田野绿世界现场门票多少钱? 佛冈田野绿世界门票预订?田野绿世界优惠票多少钱? 一叶知秋 看尽四川十大最美秋色 敏捷黄金海岸水晶湖有什么玩的?阳江敏捷黄金海岸水晶湖项目有什么? 澳门都有哪些奇怪的路牌?为什么会有这么奇怪的街道和路牌名? 澳门议事亭附近有什么好吃的?有哪些美食? 香港迪士尼乐园能带东西和吃的进去吗? 澳门购物哪里最好?具体地址在哪里? SQCA5A271JATME Datasheet SQCA5A271JATME Datasheet 08055C682MAT2A Datasheet 08055C682MAT2A Datasheet AQ12EA3R9DAJWE Datasheet AQ12EA3R9DAJWE Datasheet 吉林参团去港澳旅游 吉林参团去港澳旅游 吉林参团去港澳旅游 南通去港澳游 南通去港澳游 南通去港澳游 义乌去港澳旅游 义乌去港澳旅游 义乌去港澳旅游