Comment trouver le Kth plus grand élément en Java

1. Introduction

Dans cet article, nous présenterons différentes solutions pour trouver le k ème élément le plus grand dans une séquence de nombres uniques. Nous utiliserons un tableau d'entiers pour nos exemples.

Nous parlerons également de la complexité temporelle moyenne et dans le pire des cas de chaque algorithme.

2. Solutions

Explorons maintenant quelques solutions possibles - l'une utilisant un tri simple et deux utilisant l'algorithme de sélection rapide dérivé du tri rapide.

2.1. Tri

Lorsque nous réfléchissons au problème, la solution la plus évidente qui nous vient à l'esprit est peut-être de trier le tableau .

Définissons les étapes requises:

  • Trier le tableau par ordre croissant
  • Comme le dernier élément du tableau serait le plus grand élément, le k ème élément le plus grand serait au xème index, où x = longueur (tableau) - k

Comme nous pouvons le voir, la solution est simple mais nécessite le tri de l'ensemble du tableau. Par conséquent, la complexité temporelle sera O (n * logn) :

public int findKthLargestBySorting(Integer[] arr, int k) { Arrays.sort(arr); int targetIndex = arr.length - k; return arr[targetIndex]; }

Une autre approche consiste à trier le tableau par ordre décroissant et à simplement renvoyer l'élément sur le (k-1) ème index:

public int findKthLargestBySortingDesc(Integer[] arr, int k) { Arrays.sort(arr, Collections.reverseOrder()); return arr[k-1]; }

2.2. Sélection rapide

Cela peut être considéré comme une optimisation de l'approche précédente. En cela, nous choisissons le QuickSort pour le tri. En analysant l'énoncé du problème, nous nous rendons compte que nous n'avons pas réellement besoin de trier le tableau entier - nous avons seulement besoin de réorganiser son contenu pour que le k ème élément du tableau soit le k ème plus grand ou plus petit.

Dans QuickSort, nous sélectionnons un élément pivot et le déplaçons dans sa position correcte. Nous partitionnons également le tableau autour de lui. Dans QuickSelect, l'idée est de s'arrêter au point où le pivot lui-même est le k ème plus grand élément.

Nous pouvons optimiser davantage l'algorithme si nous ne répétons pas les deux côtés gauche et droit du pivot. Il suffit de répéter pour l'un d'entre eux en fonction de la position du pivot.

Regardons les idées de base de l'algorithme QuickSelect:

  • Choisissez un élément pivot et partitionnez le tableau en conséquence
    • Choisissez l'élément le plus à droite comme pivot
    • Remaniez le tableau de sorte que l'élément pivot soit placé à sa juste place - tous les éléments inférieurs au pivot seraient à des index inférieurs, et les éléments supérieurs au pivot seraient placés à des index plus élevés que le pivot
  • Si pivot est placé au k ème élément du tableau, quittez le processus, car pivot est le k ème élément le plus grand
  • Si la position du pivot est supérieure à k, continuez le processus avec le sous-tableau gauche, sinon, répétez le processus avec le sous-tableau droit

Nous pouvons écrire une logique générique qui peut également être utilisée pour trouver le k e plus petit élément. Nous définirons une méthode findKthElementByQuickSelect () qui retournera le k ème élément du tableau trié.

Si nous trions le tableau par ordre croissant, le k ème élément d'un tableau sera le k ème plus petit élément. Pour trouver le k ème plus grand élément, nous pouvons passer k = length (Array) - k.

Implémentons cette solution:

public int findKthElementByQuickSelect(Integer[] arr, int left, int right, int k) { if (k >= 0 && k  k) { return findKthElementByQuickSelect(arr, left, pos - 1, k); } return findKthElementByQuickSelect(arr, pos + 1, right, k - pos + left - 1); } return 0; }

Maintenant, implémentons la méthode de partition , qui sélectionne l'élément le plus à droite comme pivot, le met à l'index approprié et partitionne le tableau de telle manière que les éléments aux index inférieurs doivent être inférieurs à l'élément pivot.

De même, les éléments à des index plus élevés seront supérieurs à l'élément pivot:

public int partition(Integer[] arr, int left, int right) { int pivot = arr[right]; Integer[] leftArr; Integer[] rightArr; leftArr = IntStream.range(left, right) .filter(i -> arr[i]  arr[i]) .boxed() .toArray(Integer[]::new); rightArr = IntStream.range(left, right) .filter(i -> arr[i] > pivot) .map(i -> arr[i]) .boxed() .toArray(Integer[]::new); int leftArraySize = leftArr.length; System.arraycopy(leftArr, 0, arr, left, leftArraySize); arr[leftArraySize+left] = pivot; System.arraycopy(rightArr, 0, arr, left + leftArraySize + 1, rightArr.length); return left + leftArraySize; }

Il existe une approche itérative plus simple pour réaliser le partitionnement:

public int partitionIterative(Integer[] arr, int left, int right) { int pivot = arr[right], i = left; for (int j = left; j <= right - 1; j++) { if (arr[j] <= pivot) { swap(arr, i, j); i++; } } swap(arr, i, right); return i; } public void swap(Integer[] arr, int n1, int n2) { int temp = arr[n2]; arr[n2] = arr[n1]; arr[n1] = temp; }

Cette solution fonctionne en temps O (n) en moyenne. Cependant, dans le pire des cas, la complexité temporelle sera O (n ^ 2) .

2.3. QuickSelect avec partition aléatoire

Cette approche est une légère modification de l'approche précédente. Si le tableau est presque / entièrement trié et si nous choisissons l'élément le plus à droite comme pivot, la partition des sous-tableaux gauche et droit sera très inégale.

Cette méthode suggère de choisir l'élément de pivot initial de manière aléatoire. Nous n'avons cependant pas besoin de changer la logique de partitionnement.

Au lieu d'appeler partition , nous appelons la méthode randomPartition , qui sélectionne un élément aléatoire et l'échange avec l'élément le plus à droite avant d'appeler finalement la méthode de partition .

Implémentons la randomPartition méthode:

public int randomPartition(Integer arr[], int left, int right) { int n = right - left + 1; int pivot = (int) (Math.random()) * n; swap(arr, left + pivot, right); return partition(arr, left, right); }

Cette solution fonctionne mieux que le cas précédent dans la plupart des cas.

La complexité temporelle attendue de QuickSelect aléatoire est O (n) .

Cependant, la pire complexité temporelle reste O (n ^ 2) .

3. Conclusion

Dans cet article, nous avons discuté de différentes solutions pour trouver le k e élément le plus grand (ou le plus petit) dans un tableau de nombres uniques. La solution la plus simple consiste à trier le tableau et à renvoyer le k ème élément. Cette solution a une complexité temporelle de O (n * logn) .

Nous avons également discuté de deux variantes de Quick Select. Cet algorithme n'est pas simple mais il a une complexité temporelle de O (n) dans les cas moyens.

Comme toujours, le code complet de l'algorithme peut être trouvé sur GitHub.