Angenommen, es handelt sich um ein geordnetes zweidimensionales Array, wobei jede Zeile von links nach rechts und jede Spalte von oben nach unten zunimmt. So vervollständigen Sie eine Funktion: Geben Sie ein solches zweidimensionales Array und eine Ganzzahl ein und bestimmen Sie, ob die Ganzzahl vorhanden ist befindet sich in diesem zweidimensionalen Array.
Nehmen Sie ein 4×4 geordnetes zweidimensionales Array an:
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
Die gesuchte Zahl ist 6.
Die Kernidee des Algorithmus besteht darin, zuerst die Zahl 9 in der oberen linken Ecke zu nehmen. Da 9 größer als 6 ist, können Sie Zahlen größer als 9, also die vierte Spalte, ausschließen und dann 8 nehmen. Schließen Sie die dritte Spalte aus und nehmen Sie dann 2. Wenn sie kleiner als 6 ist, können Sie Zahlen ausschließen, die kleiner als 2 sind, dh die erste Zeile. Nehmen Sie auf die gleiche Weise 4, schließen Sie die zweite Zeile aus, nehmen Sie 7 und schließen Sie die aus zweite Spalte, nimm 4, schließe die dritte Zeile aus, nimm 6, gleich, gib true zurück.
Hier verwenden wir Rekursion, um es zu implementieren. Der Code lautet:
Kopieren Sie den Codecode wie folgt:
öffentliche Klasse FindMatrixNumber {
private statische FindMatrixNumber-Instanz;
privater statischer boolescher Wert gefunden = false;
öffentliche statische FindMatrixNumber getInstance() {
if (instance == null) {
Instanz = neue FindMatrixNumber();
}
Rückgabeinstanz;
}
public static boolean find(int matrix[][], int number) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
} anders {
System.out.println("****Suche starten****");
findMatrixNumber(matrix, matrix.length, 0, matrix[0].length,
Nummer);
System.out.println("****Ende der Suche*****");
}
Rückgabe gefunden;
}
private static void findMatrixNumber(int matrix[][], int rows, int row,
int Spalten, int Zahl) {
if (Zeile > Zeilen - 1)
zurückkehren;
int CornerNumber = Matrix[Zeile][Spalten - 1];
System.out.println(cornerNumber);
if (cornerNumber == number) {
gefunden = wahr;
zurückkehren;
} else if (cornerNumber < Zahl) {
findMatrixNumber(matrix, rows, ++row, columns, number);
} else if (cornerNumber > number) {
findMatrixNumber(matrix, rows, row, --columns, number);
}
}
}
Der Testcode lautet:
Kopieren Sie den Codecode wie folgt:
öffentliche Klasse 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));
}
}
Das Ergebnis der Ausführung des Testcodes ist:
Kopieren Sie den Codecode wie folgt:
****Beginnen Sie mit der Suche****
9
8
2
4
7
4
6
*****Finde beenden*****
WAHR