用遞歸查找有序二維數(shù)組的方法詳解
更新時(shí)間：2013年06月04日 17:43:46 作者：
本篇文章是對(duì)用遞歸查找有序二維數(shù)組的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
假設(shè)給定一個(gè)有序二維數(shù)組，每一行都是從左到右遞增，每一列都是從上到下遞增，如何完成一個(gè)函數(shù)，輸入這樣一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷這個(gè)整數(shù)是否在這個(gè)二維數(shù)組中。
假設(shè)一個(gè)4×4的有序二維數(shù)組：
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
要查找的數(shù)字為6。
算法的核心思想是，先取最左上角的數(shù)字9,因?yàn)?比6大，所以可以排除比9大的數(shù)字，也就是第四列，然后取8，同理排除第三列，再取2，比6小，可排除比2小的數(shù)字，也就是第一行，同理取4，排除第二行，取7，排除第二列，取4，排除第三行，取6，相等，返回true。
這里我們用遞歸實(shí)現(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);
}
}
}
測(cè)試代碼為：
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));
}
}
測(cè)試代碼運(yùn)行結(jié)果為：
****Start finding****
9
8
2
4
7
4
6
*****End finding*****
true
假設(shè)一個(gè)4×4的有序二維數(shù)組：
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
要查找的數(shù)字為6。
算法的核心思想是，先取最左上角的數(shù)字9,因?yàn)?比6大，所以可以排除比9大的數(shù)字，也就是第四列，然后取8，同理排除第三列，再取2，比6小，可排除比2小的數(shù)字，也就是第一行，同理取4，排除第二行，取7，排除第二列，取4，排除第三行，取6，相等，返回true。
這里我們用遞歸實(shí)現(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);
}
}
}
測(cè)試代碼為：
復(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));
}
}
測(cè)試代碼運(yùn)行結(jié)果為：
復(fù)制代碼 代碼如下:
****Start finding****
9
8
2
4
7
4
6
*****End finding*****
true
您可能感興趣的文章:
- 歸并算法之有序數(shù)組合并算法實(shí)現(xiàn)
- java實(shí)現(xiàn)向有序數(shù)組中插入一個(gè)元素實(shí)例
- php實(shí)現(xiàn)有序數(shù)組打印或排序的方法【附Python、C及Go語言實(shí)現(xiàn)代碼】
- Python實(shí)現(xiàn)二維有序數(shù)組查找的方法
- php判斷一個(gè)數(shù)組是否為有序的方法
- C語言實(shí)現(xiàn)在數(shù)組A上有序合并數(shù)組B的方法
- js有序數(shù)組的連接問題
- javascript 折半查找字符在數(shù)組中的位置(有序列表)
- 合并有序數(shù)組的實(shí)現(xiàn)（java與C語言）
相關(guān)文章
這篇文章主要介紹了java 中clone()的使用方法的相關(guān)資料,希望通過本文能幫助大家能掌握clone（）的克隆方法，需要的朋友可以參考下2017-09-09
文章總結(jié)了Java 8中流(Stream) API的多種常用方法,包括創(chuàng)建流、過濾、遍歷、分組、排序、去重、查找、匹配、轉(zhuǎn)換、歸約、打印日志、最大最小值、統(tǒng)計(jì)、連接、函數(shù)式接口等,展示了流API在處理集合數(shù)據(jù)時(shí)的強(qiáng)大和靈活性,感興趣的朋友跟隨小編一起看看吧2025-01-01
解決RedisTemplate存儲(chǔ)至緩存數(shù)據(jù)出現(xiàn)亂碼的情況
這篇文章主要介紹了解決RedisTemplate存儲(chǔ)至緩存數(shù)據(jù)出現(xiàn)亂碼的情況，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2021-03-03
Java7之forkjoin簡(jiǎn)介_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
Java7引入了Fork Join的概念，來更好的支持并行運(yùn)算。接下來通過本文給大家分享Java7之forkjoin簡(jiǎn)介，感興趣的朋友一起看看吧2017-06-06
這篇文章主要介紹了java?讀寫鎖的使用及它的優(yōu)點(diǎn)，讀寫鎖的特點(diǎn)就是是讀讀不互斥、讀寫互斥、寫寫互斥，下面具體使用分享需要的小伙伴可以參考一下2022-05-05
Java中byte輸出write到文件的實(shí)現(xiàn)方法講解
今天小編就為大家分享一篇關(guān)于Java中byte輸出write到文件的實(shí)現(xiàn)方法講解，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-03-03
這篇文章主要介紹了java 排序算法之快速排序，文中通過圖片和代碼講解相關(guān)知識(shí)非常詳細(xì)，大家如果有需要的話可以參考一下這篇文章2021-09-09
在介紹RabbitMQ之前實(shí)現(xiàn)要介紹一下MQ，MQ是什么？MQ全稱是Message Queue，可以理解為消息隊(duì)列的意思，簡(jiǎn)單來說就是消息以管道的方式進(jìn)行傳遞。RabbitMQ是一個(gè)實(shí)現(xiàn)了AMQP（Advanced Message Queuing Protocol）高級(jí)消息隊(duì)列協(xié)議的消息隊(duì)列服務(wù)，用Erlang語言的2021-11-11
Netty是由JBOSS提供的一個(gè)Java開源框架。Netty提供異步的、事件驅(qū)動(dòng)的網(wǎng)絡(luò)應(yīng)用程序框架和工具，用以快速開發(fā)高性能、高可靠性的網(wǎng)絡(luò)服務(wù)器和客戶端程序。下面這篇文章主要給大家介紹了關(guān)于Netty基礎(chǔ)使用的相關(guān)資料，需要的朋友可以參考下。2017-05-05
這篇文章主要介紹了詳解maven的install的作用,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09