用递归查找有序二维数组的方法详解
用递归查找有序二维数组的方法详解
发布时间:2016-12-28 来源:查字典编辑
摘要:假设给定一个有序二维数组,每一行都是从左到右递增,每一列都是从上到下递增,如何完成一个函数,输入这样一个二维数组和一个整数,判断这个整数是否...

假设给定一个有序二维数组,每一行都是从左到右递增,每一列都是从上到下递增,如何完成一个函数,输入这样一个二维数组和一个整数,判断这个整数是否在这个二维数组中。

假设一个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

推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关阅读
网友关注
最新Java学习
热门Java学习
编程开发子分类