用遞歸查找有序二維數(shù)組的方法詳解
更新時間:2013年06月04日 17:43:46 作者:
本篇文章是對用遞歸查找有序二維數(shù)組的方法進行了詳細的分析介紹,需要的朋友參考下
假設給定一個有序二維數(shù)組,每一行都是從左到右遞增,每一列都是從上到下遞增,如何完成一個函數(shù),輸入這樣一個二維數(shù)組和一個整數(shù),判斷這個整數(shù)是否在這個二維數(shù)組中。
假設一個4×4的有序二維數(shù)組:
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
要查找的數(shù)字為6。
算法的核心思想是,先取最左上角的數(shù)字9,因為9比6大,所以可以排除比9大的數(shù)字,也就是第四列,然后取8,同理排除第三列,再取2,比6小,可排除比2小的數(shù)字,也就是第一行,同理取4,排除第二行,取7,排除第二列,取4,排除第三行,取6,相等,返回true。
這里我們用遞歸實現(xiàn),代碼為:
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
假設一個4×4的有序二維數(shù)組:
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
要查找的數(shù)字為6。
算法的核心思想是,先取最左上角的數(shù)字9,因為9比6大,所以可以排除比9大的數(shù)字,也就是第四列,然后取8,同理排除第三列,再取2,比6小,可排除比2小的數(shù)字,也就是第一行,同理取4,排除第二行,取7,排除第二列,取4,排除第三行,取6,相等,返回true。
這里我們用遞歸實現(xiàn),代碼為:
復制代碼 代碼如下:
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
相關文章
解決RedisTemplate存儲至緩存數(shù)據(jù)出現(xiàn)亂碼的情況
這篇文章主要介紹了解決RedisTemplate存儲至緩存數(shù)據(jù)出現(xiàn)亂碼的情況,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2021-03-03
Java7之forkjoin簡介_動力節(jié)點Java學院整理
Java7引入了Fork Join的概念,來更好的支持并行運算。接下來通過本文給大家分享Java7之forkjoin簡介,感興趣的朋友一起看看吧2017-06-06
Java中byte輸出write到文件的實現(xiàn)方法講解
今天小編就為大家分享一篇關于Java中byte輸出write到文件的實現(xiàn)方法講解,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2019-03-03

