Comptage des fréquences et regroupement
Utilisez Counter et defaultdict pour compter les fréquences de caractères, regrouper les anagrammes par clé triée et trouver les éléments les plus fréquents.
Comptage des fréquences et regroupement est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Comptage des fréquences : le schéma fondamental
Le comptage des fréquences fait partie des schémas les plus polyvalents des entretiens de programmation. En comptant le nombre d’occurrences de chaque élément dans une liste ou une chaîne, vous pouvez répondre à des questions sur les doublons, les anagrammes, les éléments les plus fréquents et les arrangements valides en O(n) — bien plus efficacement qu’avec l’alternative consistant à trier puis à parcourir, en O(n log n).
Counter et defaultdict(int) sont les outils Python standard. Tous deux créent une correspondance entre un élément et son nombre d’occurrences ; Counter prend également en charge les opérations arithmétiques et most_common.
from collections import Counter
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
freq = Counter(words)
print(freq) # Counter({'apple':3,'banana':2,'cherry':1})
print(freq['apple']) # 3
print(freq['grape']) # 0 (not KeyError)
print(freq.most_common(2)) # [('apple',3),('banana',2)]Anagramme valide (LeetCode 242)
LeetCode 242 « Anagramme valide » : déterminez si deux chaînes sont des anagrammes l’une de l’autre. Deux chaînes sont des anagrammes si leurs fréquences de caractères sont identiques. Comparez leurs objets Counter ou triez les deux chaînes. L’utilisation de Counter est en O(n), tandis que le tri est en O(n log n). L’approche avec Counter est optimale et exprime directement la définition.
from collections import Counter
def isAnagram(s, t):
return Counter(s) == Counter(t)
# Alternative: manual frequency array for lowercase letters only
def isAnagram_arr(s, t):
if len(s) != len(t):
return False
freq = [0] * 26
for c in s: freq[ord(c) - ord('a')] += 1
for c in t: freq[ord(c) - ord('a')] -= 1
return all(f == 0 for f in freq)
print(isAnagram('anagram', 'nagaram')) # True
print(isAnagram('rat', 'car')) # False
print(isAnagram_arr('listen', 'silent')) # TrueRegrouper les anagrammes (LeetCode 49)
LeetCode 49 « Regrouper les anagrammes » : étant donné une liste de chaînes, regroupez toutes les anagrammes ensemble. L’idée essentielle est que les anagrammes ont la même séquence de caractères triée. Utilisez un defaultdict(list) dont la clé est le tuple trié de la chaîne (les tuples sont hachables). Chaque groupe s’accumule sous la même clé. Complexité temporelle : O(n × L log L), où L est la longueur maximale d’une chaîne.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # hashable canonical form
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]
# Alternative key: tuple of 26 character counts (O(L) not O(L log L))
def groupAnagrams_v2(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(ord(c) - ord('a') for c in sorted(s))
groups[tuple(Counter(s)[chr(ord('a')+i)] for i in range(26))].append(s)
return list(groups.values())
Éléments les plus fréquents (LeetCode 347)
LeetCode 347 « Éléments les plus fréquents » : renvoyez les k éléments les plus fréquents. Une approche directe est en O(n log n) : comptez les fréquences, triez par fréquence décroissante, puis prenez les k premiers éléments. L’approche optimale en O(n) utilise le tri par compartiments : créez des compartiments indexés par fréquence (de 1 à n), placez chaque élément dans le compartiment correspondant à sa fréquence, puis parcourez les compartiments de la fréquence la plus élevée à la plus faible en recueillant k éléments.
from collections import Counter
def topKFrequent(nums, k):
freq = Counter(nums)
# Bucket sort by frequency
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
result.extend(buckets[i])
if len(result) >= k:
return result[:k]
return result
print(topKFrequent([1,1,1,2,2,3], 2)) # [1, 2]
print(topKFrequent([1], 1)) # [1]Trier les caractères par fréquence (LeetCode 451)
LeetCode 451 « Trier les caractères par fréquence » : réorganisez une chaîne afin que les caractères apparaissent par ordre décroissant de fréquence. Comptez les fréquences, triez les caractères par fréquence décroissante, puis concaténez-les. L’utilisation de most_common est l’approche Python la plus claire. Complexité temporelle : O(n log n) pour trier les caractères distincts par fréquence.
from collections import Counter
def frequencySort(s):
freq = Counter(s)
return ''.join(ch * count for ch, count in freq.most_common())
print(frequencySort('tree')) # 'eetr' or 'eert'
print(frequencySort('cccaaa')) # 'cccaaa' or 'aaaccc'
print(frequencySort('Aabb')) # 'bbAa' or 'bbaA'Ordonnanceur de tâches (LeetCode 621)
LeetCode 621 « Ordonnanceur de tâches » : étant donné des tâches et un délai d’attente n, trouvez le temps minimal nécessaire pour terminer toutes les tâches. L’idée essentielle est que la tâche la plus fréquente détermine la structure. Disposez max_count copies de la tâche la plus fréquente en les séparant par (n) intervalles. Le temps minimal total = max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks). S’il existe suffisamment de tâches différentes pour remplir les intervalles, le temps d’inactivité est nul.
from collections import Counter
def leastInterval(tasks, n):
freq = Counter(tasks)
max_count = max(freq.values())
# How many tasks share the max frequency
num_max = sum(1 for v in freq.values() if v == max_count)
# Minimum slots needed based on most frequent task
min_slots = (max_count - 1) * (n + 1) + num_max
return max(min_slots, len(tasks))
print(leastInterval(['A','A','A','B','B','B'], 2)) # 8
print(leastInterval(['A','A','A','B','B','B'], 0)) # 6
print(leastInterval(['A','A','A','A','B','B','B','C','C','D'], 2)) # 10Vote majoritaire avec Counter
LeetCode 169 « Élément majoritaire » : trouvez l’élément apparaissant plus de n/2 fois. Bien que le vote de Boyer-Moore soit la solution optimale avec une complexité spatiale de O(1), l’utilisation de Counter.most_common(1) permet de résoudre directement le problème en O(n) avec une complexité spatiale de O(n). Pour les entretiens qui imposent une complexité spatiale de O(1), présentez Boyer-Moore comme approfondissement ; lorsque l’espace supplémentaire est autorisé, Counter est plus clair.
from collections import Counter
def majorityElement_counter(nums):
freq = Counter(nums)
return freq.most_common(1)[0][0]
# Boyer-Moore O(1) space
def majorityElement_moore(nums):
candidate, count = None, 0
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
nums = [2, 2, 1, 1, 2, 2, 2]
print(majorityElement_counter(nums)) # 2
print(majorityElement_moore(nums)) # 2Premier caractère non répétitif
LeetCode 387 « Premier caractère unique dans une chaîne » : trouvez l’indice du premier caractère apparaissant exactement une fois. Approche en deux passages : le premier construit un comptage des fréquences ; le second trouve le premier caractère dont le nombre d’occurrences vaut 1. Complexité temporelle : O(n), espace : O(1), puisque l’alphabet est limité à 26 caractères.
from collections import Counter
def firstUniqChar(s):
freq = Counter(s)
for i, ch in enumerate(s):
if freq[ch] == 1:
return i
return -1
print(firstUniqChar('leetcode')) # 0 (l)
print(firstUniqChar('loveleetcode')) # 2 (v)
print(firstUniqChar('aabb')) # -1Somme d’un sous-tableau égale à K (LeetCode 560)
LeetCode 560 « Somme d’un sous-tableau égale à K » : comptez les sous-tableaux dont la somme vaut k. La méthode par force brute est en O(n²). L’approche en O(n) consiste à maintenir une somme préfixe cumulée et une table de fréquences des sommes préfixes déjà rencontrées. Pour chaque position i, le nombre de sous-tableaux se terminant en i et dont la somme vaut k est égal au nombre de sommes préfixes antérieures égales à (current_prefix_sum - k). Initialisez la table avec {0: 1} pour gérer les sous-tableaux commençant à l’indice 0.
from collections import defaultdict
def subarraySum(nums, k):
freq = defaultdict(int)
freq[0] = 1 # prefix sum of 0 seen once (empty prefix)
prefix_sum = 0
count = 0
for num in nums:
prefix_sum += num
# How many earlier prefix sums allow a k-sum subarray ending here
count += freq[prefix_sum - k]
freq[prefix_sum] += 1
return count
print(subarraySum([1, 1, 1], 2)) # 2
print(subarraySum([1, 2, 3], 3)) # 2
print(subarraySum([1, -1, 1, -1, 1], 0)) # 4Opérations arithmétiques et intersection avec Counter
Counter prend en charge les opérations arithmétiques : + fusionne les compteurs (en additionnant leurs nombres), - soustrait (en limitant le résultat à 0), & prend le minimum (intersection) et | prend le maximum (union). Ces opérations simplifient des problèmes comme « trouver les caractères communs à plusieurs chaînes » ou « supprimer le moins de caractères possible pour transformer une chaîne en anagramme d’une autre ».
from collections import Counter
A = Counter('abccdd')
B = Counter('ccdde')
print('Add: ', dict(A + B)) # sum of counts
print('Subtract: ', dict(A - B)) # A - B, clipped at 0
print('Intersect:', dict(A & B)) # min of shared counts
print('Union: ', dict(A | B)) # max counts
# Min steps to make s anagram of t (LeetCode 1347)
s, t = 'leetcode', 'practice'
diff = Counter(t) - Counter(s)
print('Chars to add:', sum(diff.values())) # 5Résumé : quand utiliser le comptage des fréquences
Utilisez le comptage des fréquences lorsque le problème consiste à : vérifier si deux chaînes sont équivalentes à une réorganisation près (anagramme), trouver les éléments les plus ou les moins fréquents, vérifier qu’une collection contient les bons « ingrédients », ou transformer un problème de sous-tableau ou de sous-chaîne en problème de somme préfixe avec table. L’idée essentielle est que l’ordre au sein d’un groupe n’a pas d’importance — seuls les nombres d’occurrences comptent.
Utilisez toujours Counter pour privilégier la clarté ; remplacez-le par un simple dict ou un tableau uniquement si vous avez besoin d’un contrôle plus précis ou d’un espace strictement en O(1) avec un alphabet borné.
Vérification rapide
Évaluez votre compréhension des concepts de Structures de données et algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : Counter fournit un comptage des fréquences en O(n), avec most_common, des opérateurs arithmétiques et un accès renvoyant zéro par défaut, le regroupement par forme canonique (tuple trié) résout le problème du regroupement d’anagrammes en O(nL log L), et l’utilisation d’une somme préfixe avec une table de fréquences transforme le problème de la somme d’un sous-tableau égale à k, de O(n²) à O(n). Ensuite, nous aborderons le problème de la plus longue séquence consécutive et la conception d’un cache LRU.
Questions Fréquemment Posées
La leçon « Comptage des fréquences et regroupement » est-elle gratuite ?
Oui — le texte complet de « Comptage des fréquences et regroupement » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Comptage des fréquences et regroupement » ?
Utilisez Counter et defaultdict pour compter les fréquences de caractères, regrouper les anagrammes par clé triée et trouver les éléments les plus fréquents. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Comptage des fréquences et regroupement » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Fonction de hachage : fonctionnement interne et gestion des collisions
- Two-Sum et ses nombreuses variantes
- Comptage des fréquences et regroupement
- Plus longue séquence consécutive et cache LRU