Après avoir répondu à cette question, vous penserez d'abord au tri. Après le tri, sélectionnez le plus grand nombre K. Sélection de tri Le tri rapide est un meilleur choix.
Bon, passons à la première solution : un tri rapide
Le code est le suivant
Copiez le code comme suit :
public static void quickSort(int[] arr, int start, int end) {
si (début < fin) {
clé int = arr[début];
int right = début ;
int gauche = fin ;
tandis que (droite < gauche) {
while (droite < gauche && arr[gauche] > touche) {
gauche --;
}
si (droite < gauche) {
arr[droite] = arr[gauche];
}
while (droite < gauche && arr[droite] <= touche) {
c'est vrai++;
}
si (droite < gauche) {
arr[gauche] = arr[droite];
}
}
arr[droite] = clé ;
quickSort(arr, start, right-1);
quickSort(arr, gauche+1, fin);
}
}
Après un tri rapide, le tableau sera dans l'ordre. Le tri ci-dessus va de petit à grand, notre résultat devrait donc être le suivant.
Copiez le code comme suit : int k = 4;
pour (int i=arr.length-1; i>=arr.length-k; i--) {
System.out.println(arr[i]+" ");
}
. La première solution est déjà bonne, mais existe-t-il une meilleure solution ?
La réponse est oui ! Nous pouvons choisir un tri partiel, puis utiliser le tri par sélection pour résoudre ce problème.
Le code est le suivant :
Copiez le code comme suit : public static int[] selectSortK(int[] arr, int k) {
if(arr == null || arr.length == 0) {
renvoie null ;
}
int[] newArr = nouveau int[k];
List<Integer> list = new ArrayList<Integer>();//Enregistrez l'indice du nombre maximum à chaque fois
pour (int i=0; i<k; i++) {
int maxValue = Integer.MIN_VALUE; //Valeur maximale
int maxIndex = je;
pour (int j=0; j<arr.length; j++) {
if (arr[j] > maxValue && !list.contains(j) ) {
valeurmax = arr[j];
maxIndex = j;
}
}
if (!list.contains(maxIndex)) {//S'il n'existe pas, ajoutez-le
list.add(maxIndex);
newArr[i] = valeurmax;
}
}
retourner newArr ;
}