Supposons qu'un tableau bidimensionnel ordonné soit donné, chaque ligne augmente de gauche à droite et chaque colonne augmente de haut en bas. Comment compléter une fonction, saisir un tel tableau bidimensionnel et un entier et déterminer si l'entier est un entier. est dans ce tableau bidimensionnel.
Supposons un tableau bidimensionnel ordonné 4 × 4 :
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
Le nombre que vous recherchez est le 6.
L'idée principale de l'algorithme est de prendre d'abord le nombre 9 dans le coin supérieur gauche, car 9 est supérieur à 6, vous pouvez exclure les nombres supérieurs à 9, c'est-à-dire la quatrième colonne, puis prendre 8. De même, excluez la troisième colonne, puis prenez 2. S'il est inférieur à 6, vous pouvez exclure les nombres inférieurs à 2, c'est-à-dire la première ligne. De la même manière, prenez 4, excluez la deuxième ligne, prenez 7, excluez le. deuxième colonne, prenez 4, excluez la troisième ligne, prenez 6, égal, retournez vrai.
Ici nous utilisons la récursivité pour l'implémenter, le code est :
Copiez le code comme suit :
classe publique FindMatrixNumber {
instance FindMatrixNumber statique privée ;
booléen statique privé trouvé = faux ;
public statique FindMatrixNumber getInstance() {
si (instance == null) {
instance = nouveau FindMatrixNumber();
}
instance de retour ;
}
recherche booléenne statique publique (int matrice [][], nombre int) {
if (matrix == null || matrice.longueur == 0 || matrice[0].longueur == 0) {
renvoie faux ;
} autre {
System.out.println("****Commencer à rechercher ****");
findMatrixNumber(matrice, matrice.longueur, 0, matrice[0].longueur,
nombre);
System.out.println("****Fin de la recherche*****");
}
retour trouvé ;
}
vide statique privé findMatrixNumber (int matrice [][], lignes int, ligne int,
colonnes int, nombre int) {
si (ligne > lignes - 1)
retour;
int cornerNumber = matrice[ligne][colonnes - 1];
System.out.println(cornerNumber);
if (numéro de coin == numéro) {
trouvé = vrai ;
retour;
} else if (cornerNumber < nombre) {
findMatrixNumber(matrice, lignes, ++ligne, colonnes, nombre);
} sinon si (numéro de coin > numéro) {
findMatrixNumber(matrice, lignes, ligne, --columns, nombre);
}
}
}
Le code du test est :
Copiez le code comme suit :
classe publique TestFindMatrixNumber {
public static void main (String[] arguments) {
int matrice[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}} ;
System.out.println(FindMatrixNumber.find(matrice, 6));
}
}
Le résultat de l'exécution du code de test est :
Copiez le code comme suit :
****Commencez à trouver****
9
8
2
4
7
4
6
*****Fin de la recherche*****
vrai