Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Regrouper, compter, trouver le plus fréquent

Regrouper, compter, trouver le plus fréquent

Maps, Sets et regroupementsintermediaire

Trois motifs couvrent la quasi-totalité des exercices de regroupement.

1. Regrouper par clé

Map<String, List<Produit>> parCategorie = new HashMap<>();
for (Produit p : produits)
    parCategorie.computeIfAbsent(p.categorie(), k -> new ArrayList<>()).add(p);

La difficulté n'est jamais le code, c'est le choix de la clé : catégorie, première lettre, lettres triées pour les anagrammes, longueur…

2. Compter, puis trouver le maximum

Map<String, Integer> f = new HashMap<>();
for (String mot : mots) f.merge(mot, 1, Integer::sum);

String plusFrequent = f.entrySet().stream()
    .max(Map.Entry.comparingByValue())
    .map(Map.Entry::getKey)
    .orElseThrow();

3. Le top K — deux bonnes réponses :

// Tas de taille K : O(n log K)
PriorityQueue<Map.Entry<String, Integer>> tas =
    new PriorityQueue<>(Map.Entry.comparingByValue());     // min-heap
for (var e : f.entrySet()) {
    tas.offer(e);
    if (tas.size() > k) tas.poll();                        // on jette le plus petit
}

// Tri par comptage : O(n), car une fréquence est bornée par n
List<String>[] parFrequence = new List[n + 1];

Et une astuce à connaître : l'élément majoritaire (plus de n/2 occurrences) se trouve en O(1) en espace avec le vote de Boyer-Moore.

Les termes à connaître

Regroupement par clé

Rassembler les éléments partageant une même caractéristique dans une Map<Clé, List<Élément>>. La base de tout traitement « par catégorie ».

Clé de regroupement

La fonction qui extrait la caractéristique commune : la catégorie, la première lettre, les lettres triées (anagrammes). Choisir la bonne clé est tout le problème.

Élément majoritaire

Celui qui apparaît strictement plus de n/2 fois. Se trouve en O(n) avec une Map — ou en O(1) en espace avec l'algorithme de vote de Boyer-Moore.

Vote de Boyer-Moore

Un candidat et un compteur : on incrémente si l'élément courant est le candidat, on décrémente sinon, on change de candidat quand le compteur atteint zéro. O(n) temps, O(1) espace.

Top K

Les K éléments les plus fréquents. Se résout par comptage puis tri (O(n log n)), ou par comptage puis tas de taille K (O(n log K)).

Tri par comptage (*bucket sort*)

Quand les valeurs sont bornées — ici, une fréquence ne dépasse pas n — on range par fréquence dans un tableau de listes : le top K devient O(n).

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.