Supongamos que se proporciona una matriz bidimensional ordenada, cada fila aumenta de izquierda a derecha y cada columna aumenta de arriba a abajo. Cómo completar una función, ingrese dicha matriz bidimensional y un número entero, y determine si es un número entero. está en esta matriz bidimensional.
Supongamos una matriz bidimensional ordenada de 4 × 4:
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
El número que buscas es el 6.
La idea central del algoritmo es tomar primero el número 9 en la esquina superior izquierda. Debido a que 9 es mayor que 6, puede excluir los números mayores que 9, es decir, la cuarta columna, y luego tomar 8. De manera similar, excluya la tercera columna y luego tome 2. Si es menor que 6, puede excluir números menores que 2, es decir, la primera fila. De la misma manera, tome 4, excluya la segunda fila, tome 7, excluya el. segunda columna, toma 4, excluye la tercera fila, toma 6, igual, devuelve verdadero.
Aquí usamos recursividad para implementarlo, el código es:
Copie el código de código de la siguiente manera:
clase pública FindMatrixNumber {
instancia privada estática de FindMatrixNumber;
booleano estático privado encontrado = falso;
público estático FindMatrixNumber getInstance() {
si (instancia == nulo) {
instancia = nuevo FindMatrixNumber();
}
instancia de devolución;
}
búsqueda booleana estática pública (matriz int [] [], número int) {
if (matriz == nulo || matriz.longitud == 0 || matriz[0].longitud == 0) {
devolver falso;
} demás {
System.out.println("****Comenzar a buscar****");
findMatrixNumber(matriz, matriz.longitud, 0, matriz[0].longitud,
número);
System.out.println("****Fin del hallazgo*****");
}
devolución encontrada;
}
vacío estático privado findMatrixNumber(int matriz[][], int filas, int fila,
int columnas, int número) {
si (fila > filas - 1)
devolver;
int cornerNumber = matriz[fila][columnas - 1];
System.out.println(número de esquina);
if (número de esquina == número) {
encontrado = verdadero;
devolver;
} más si (Número de esquina <número) {
findMatrixNumber(matriz, filas, ++fila, columnas, número);
} else if (Número de esquina > número) {
findMatrixNumber(matriz, filas, fila, --columnas, número);
}
}
}
El código de prueba es:
Copie el código de código de la siguiente manera:
clase pública TestFindMatrixNumber {
público estático vacío principal (String [] argumentos) {
int matriz[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
System.out.println(FindMatrixNumber.find(matriz, 6));
}
}
El resultado de ejecutar el código de prueba es:
Copie el código de código de la siguiente manera:
****Comienza a buscar****
9
8
2
4
7
4
6
*****Finalizar hallazgo*****
verdadero