用递归查找有序二维数组的方法详解

2016-02-19 09:25 6 1 收藏

生活已是百般艰难,为何不努力一点。下面图老师就给大家分享用递归查找有序二维数组的方法详解,希望可以让热爱学习的朋友们体会到设计的小小的乐趣。

【 tulaoshi.com - 编程语言 】

假设给定一个有序二维数组,每一行都是从左到右递增,每一列都是从上到下递增,如何完成一个函数,输入这样一个二维数组和一个整数,判断这个整数是否在这个二维数组中。
假设一个4×4的有序二维数组:
          1          2          8          9
          2          4          9          12
          4          7          10        13
          6          8          11        15
要查找的数字为6。
算法的核心思想是,先取最左上角的数字9,因为9比6大,所以可以排除比9大的数字,也就是第四列,然后取8,同理排除第三列,再取2,比6小,可排除比2小的数字,也就是第一行,同理取4,排除第二行,取7,排除第二列,取4,排除第三行,取6,相等,返回true。
这里我们用递归实现,代码为:
代码如下:

public class FindMatrixNumber {
 private static FindMatrixNumber instance;
 private static boolean found = false;
 public static FindMatrixNumber getInstance() {
  if (instance == null) {
   instance = new FindMatrixNumber();
  }
  return instance;
 }
 public static boolean find(int matrix[][], int number) {
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
   return false;
  } else {
   System.out.println("****Start finding****");
   findMatrixNumber(matrix, matrix.length, 0, matrix[0].length,
     number);
   System.out.println("*****End finding*****");
  }
  return found;
 }
 private static void findMatrixNumber(int matrix[][], int rows, int row,
   int columns, int number) {
  if (row rows - 1)
   return;
  int cornerNumber = matrix[row][columns - 1];
  System.out.println(cornerNumber);
  if (cornerNumber == number) {
   found = true;
   return;
  } else if (cornerNumber number) {
   findMatrixNumber(matrix, rows, ++row, columns, number);
  } else if (cornerNumber number) {
   findMatrixNumber(matrix, rows, row, --columns, number);
  }
 }
}

测试代码为:
代码如下:

public class TestFindMatrixNumber {

 public static void main(String[] args) {
  int matrix[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
  System.out.println(FindMatrixNumber.find(matrix, 6));
 }

}

测试代码运行结果为:
代码如下:

****Start finding****
9
8
2
4
7
4
6
*****End finding*****
true

来源:http://www.tulaoshi.com/n/20160219/1590687.html

延伸阅读
二维码连接360助手的方法   打开电脑上的360手机助手,点击左上角开始连接--通过无线连接。 打开手机上的360手机助手,点击右上角魔法棒--扫描二维码,然后使用360手机助手扫描电脑上的二维码。
可以这样: Vector vector1=new Vector(); Vector vector2=new Vector(); ... .. HashTable numbers=new HashTable(); numbers.put("vector1",vector1); numbers.put("vector2",vector2); ...
微信二维码支付怎么用   1、打开微信,点击右下角,选择钱包,再点击左上角。 2、点击,然后点击右上角。 3、输入金额,可以点击进行文字说明,设置好后点击。 4、全部完成后,一个二维码就生成了,只需朋友用微信扫描即可完成转账。
微信二维码支付怎么生成二维码   1)打开微信,点击右下角,选择钱包,再点击左上角。   2)点击,然后点击右上角。   3)输入金额,可以点击进行文字说明,设置好后点击。   4)全部完成后,一个二维码就生成了,只需朋友用微信扫描即可完成转账。

经验教程

860

收藏

90
微博分享 QQ分享 QQ空间 手机页面 收藏网站 回到头部