用遞歸查找有序二維數(shù)組的方法詳解
更新時間：2013年06月04日 17:43:46 作者：
本篇文章是對用遞歸查找有序二維數(shù)組的方法進行了詳細的分析介紹，需要的朋友參考下
假設(shè)給定一個有序二維數(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));
}
}
測試代碼運行結(jié)果為：
****Start finding****
9
8
2
4
7
4
6
*****End finding*****
true
假設(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)，代碼為：
復(fù)制代碼 代碼如下:
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);
}
}
}
測試代碼為：
復(fù)制代碼 代碼如下:
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));
}
}
測試代碼運行結(jié)果為：
復(fù)制代碼 代碼如下:
****Start finding****
9
8
2
4
7
4
6
*****End finding*****
true
相關(guān)文章
這篇文章主要介紹了MyBatis 配置之集合的嵌套方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
JAVA面試題之Forward與Redirect的區(qū)別詳解
這篇文章主要給大家介紹了在JAVA面試中可能遇到會遇到的一道題，就是java中Forward與Redirect兩者之前的區(qū)別，文中介紹的非常詳細，對大家具有一定參考學(xué)習(xí)價值，需要的朋友們下面來一起看看吧。2017-05-05
這篇文章主要介紹了Spring中MVC模塊代碼詳解，涉及Controller的簡單介紹，具有一定借鑒價值，需要的朋友可以參考下。2017-11-11
Java基于二分搜索樹、鏈表的實現(xiàn)的集合Set復(fù)雜度分析實例詳解
這篇文章主要介紹了Java基于二分搜索樹、鏈表的實現(xiàn)的集合Set復(fù)雜度分析,結(jié)合實例形式詳細分析了Java基于二分搜索樹、鏈表的實現(xiàn)的集合Set復(fù)雜度分析相關(guān)操作技巧與注意事項,需要的朋友可以參考下2020-03-03
Java中你真的會用Constructor構(gòu)造器嗎之看完本篇你就真的會了
顯式初始化要求我們在寫程序時就確定初始值，這有時很不方便。我們可以使用構(gòu)造器(constructor)來初始化對象。構(gòu)造器可以初始化數(shù)據(jù)成員，還可以規(guī)定特定的操作。這些操作會在創(chuàng)建對象時自動執(zhí)行。下面文字將對該內(nèi)容做詳細介紹，需要的小伙伴請參考2021-09-09
今天給大家普及如何使用IDEA新建一個普通的Javaweb項目及配置tomcat的方法，在文末給大家提到如果不想每次都重啟tomcat，可以設(shè)置快捷方式，對idea新建Javaweb項目感興趣的朋友一起看看吧2021-06-06
springboot2.3 整合mybatis-plus 高級功能及用法詳解
這篇文章主要介紹了springboot2.3 整合mybatis-plus 高級功能,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-09-09
分享Spring?Cloud?OpenFeign?的五個優(yōu)化技巧
這篇文章主要分享的是Spring?Cloud?OpenFeign?的五個優(yōu)化技巧,OpenFeign?是?Spring?官方推出的一種聲明式服務(wù)調(diào)用和負載均衡組件，更多相關(guān)內(nèi)容需要的小伙伴可以參考一下2022-05-05
本文主要將Java中的IO流進行了梳理，通過將其分成字節(jié)流和字符流，以及輸入流和輸出流分別統(tǒng)計，來建立一個對 Java中IO流全局的概念，通過一些實例來演示了如何通過不同類型的流來組合實現(xiàn)強大靈活的輸入和輸出，最后介紹了同時支持輸入和輸出的 RandomAccessFile。2021-04-04
Spring Boot使用FastJson解析JSON數(shù)據(jù)的方法
本篇文章主要介紹了Spring Boot使用FastJson解析JSON數(shù)據(jù)的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-02-02