Assume that an ordered two-dimensional array is given, each row increases from left to right, and each column increases from top to bottom. How to complete a function, input such a two-dimensional array and an integer, and determine whether the integer is in in this two-dimensional array.
Assume a 4×4 ordered two-dimensional array:
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
The number you are looking for is 6.
The core idea of the algorithm is to first take the number 9 in the upper left corner. Because 9 is larger than 6, you can exclude numbers larger than 9, that is, the fourth column, and then take 8. Similarly, exclude the third column, and then take 2. If it is smaller than 6, you can exclude numbers smaller than 2, that is, the first row. In the same way, take 4, exclude the second row, take 7, exclude the second column, take 4, exclude the third row, take 6, equal, return true.
Here we use recursion to implement it, the code is:
Copy the code code as follows:
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);
}
}
}
The test code is:
Copy the code code as follows:
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));
}
}
The result of running the test code is:
Copy the code code as follows:
****Start finding****
9
8
2
4
7
4
6
*****End finding*****
true