[java] view plaincopyprint?
public class Test03 {
/**
* 在一個二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。
* 請完成一個函數(shù),輸入這樣的一個二維數(shù)組和一個整數(shù),判斷數(shù)組中是否含有該整數(shù)。
* <p/>
* 規(guī)律:首先選取數(shù)組中右上角的數(shù)字。如果該數(shù)字等于要查找的數(shù)字,查找過程結(jié)束:
* 如果該數(shù)字大于要查找的數(shù)字,剔除這個數(shù)字所在的列:如果該數(shù)字小于要查找的數(shù)字,剔除這個數(shù)字所在的行。
* 也就是說如果要查找的數(shù)字不在數(shù)組的右上角,則每-次都在數(shù)組的查找范圍中剔除)行或者一列,這樣每一步都可以縮小
* 查找的范圍,直到找到要查找的數(shù)字,或者查找范圍為空。
*
* @param matrix 待查找的數(shù)組
* @param number 要查找的數(shù)
* @return 查找結(jié)果,true找到,false沒有找到
*/
public static boolean find(int[][] matrix, int number) {
// 輸入條件判斷
if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {
return false;
}
int rows = matrix.length; // 數(shù)組的行數(shù)
int cols = matrix[1].length; // 數(shù)組行的列數(shù)
int row = 0; // 起始開始的行號
int col = cols - 1; // 起始開始的列號
// 要查找的位置確保在數(shù)組之內(nèi)
while (row >= 0 && row < rows && col >= 0 && col < cols) {
if (matrix[row][col] == number) { // 如果找到了就直接退出
return true;
} else if (matrix[row][col] > number) { // 如果找到的數(shù)比要找的數(shù)大,說明要找的數(shù)在當(dāng)前數(shù)的左邊
col--; // 列數(shù)減一,代表向左移動
} else { // 如果找到的數(shù)比要找的數(shù)小,說明要找的數(shù)在當(dāng)前數(shù)的下邊
row++; // 行數(shù)加一,代表向下移動
}
}
return false;
}
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(find(matrix, 7)); // 要查找的數(shù)在數(shù)組中
System.out.println(find(matrix, 5)); // 要查找的數(shù)不在數(shù)組中
System.out.println(find(matrix, 1)); // 要查找的數(shù)是數(shù)組中最小的數(shù)字
System.out.println(find(matrix, 15)); // 要查找的數(shù)是數(shù)組中最大的數(shù)字
System.out.println(find(matrix, 0)); // 要查找的數(shù)比數(shù)組中最小的數(shù)字還小
System.out.println(find(matrix, 16)); // 要查找的數(shù)比數(shù)組中最大的數(shù)字還大
System.out.println(find(null, 16)); // 健壯性測試,輸入空指針
}
}
http://wiki.jikexueyuan.com/project/for-offer/images/2.png" alt="" />