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).
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.