你的位置:首页 > 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