Recherche des K principaux éléments dans un tableau Java

1. Vue d'ensemble

Dans ce tutoriel, nous allons implémenter différentes solutions au problème de la recherche des k plus grands éléments dans un tableau avec Java. Pour décrire la complexité du temps, nous utiliserons la notation Big-O.

2. Solution Brute-Force

La solution par force brute à ce problème consiste à parcourir le tableau donné k fois . Dans chaque itération, nous trouverons la plus grande valeur . Ensuite, nous supprimerons cette valeur du tableau et la placerons dans la liste de sortie:

public List findTopK(List input, int k) { List array = new ArrayList(input); List topKList = new ArrayList(); for (int i = 0; i < k; i++) { int maxIndex = 0; for (int j = 1; j  array.get(maxIndex)) { maxIndex = j; } } topKList.add(array.remove(maxIndex)); } return topKList; }

Si nous supposons que n est la taille du tableau donné, la complexité temporelle de cette solution est O (n * k) . De plus, c'est la solution la plus inefficace.

3. Approche des collections Java

Cependant, des solutions plus efficaces à ce problème existent. Dans cette section, nous en expliquerons deux à l'aide des collections Java.

3.1. TreeSet

TreeSet a une structure de données d' arbre rouge-noir comme épine dorsale. En conséquence, mettre une valeur à cet ensemble coûte O (log n) . TreeSet est une collection triée. Par conséquent, nous pouvons mettre toutes les valeurs dans le TreeSet et en extraire les k premiers :

public List findTopK(List input, int k) { Set sortedSet = new TreeSet(Comparator.reverseOrder()); sortedSet.addAll(input); return sortedSet.stream().limit(k).collect(Collectors.toList()); }

La complexité temporelle de cette solution est O (n * log n) . Surtout, cela est censé être plus efficace que l'approche par force brute si k ≥ log n .

Il est important de se rappeler que TreeSet ne contient aucun doublon. En conséquence, la solution fonctionne uniquement pour un tableau d'entrée avec des valeurs distinctes.

3.2. File d'attente de priorité

PriorityQueue est une structure de données Heap en Java. Avec son aide, nous pouvons obtenir une solution O (n * log k) . De plus, ce sera une solution plus rapide que la précédente. En raison du problème mentionné, k est toujours inférieur à la taille du tableau. Donc, cela signifie que O (n * log k) ≤ O (n * log n).

L'algorithme effectue une itération une fois dans le tableau donné . À chaque itération, nous ajouterons un nouvel élément au tas. De plus, nous garderons la taille du tas inférieure ou égale à k . Nous devrons donc supprimer des éléments supplémentaires du tas et en ajouter de nouveaux. En conséquence, après avoir parcouru le tableau, le tas contiendra les k plus grandes valeurs:

public List findTopK(List input, int k) { PriorityQueue maxHeap = new PriorityQueue(); input.forEach(number -> { maxHeap.add(number); if (maxHeap.size() > k) { maxHeap.poll(); } }); List topKList = new ArrayList(maxHeap); Collections.reverse(topKList); return topKList; }

4. Algorithme de sélection

Il existe de nombreuses approches pour résoudre le problème donné. Et, bien que cela dépasse le cadre de ce didacticiel, l' utilisation de l'approche de l'algorithme de sélection sera la meilleure car elle produit une complexité temporelle linéaire.

5. Conclusion

Dans ce didacticiel, nous avons décrit plusieurs solutions pour trouver les k plus grands éléments d'un tableau.

Comme d'habitude, l'exemple de code est disponible sur sur GitHub.