Top K Frequent Elements
Vous disposez d’un tableau d’entiers nums et d’un entier k. Renvoyez les k valeurs qui apparaissent le plus souvent dans nums, en commençant par la plus fréquente. Lorsque deux valeurs apparaissent le même nombre de fois, la plus petite vient en premier.
Chaque valeur apparaît une seule fois dans la réponse, quel que soit son nombre d’occurrences dans nums, et k n’est jamais supérieur au nombre de valeurs différentes.
Fonction
- numsinteger-array
- les valeurs à compter
- kinteger
- combien de valeurs renvoyer
- Renvoieinteger-array
- les k valeurs les plus fréquentes, les plus fréquentes en premier, la plus petite valeur en premier en cas d’égalité
Contraintes
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ k, etkest inférieur ou égal au nombre de valeurs distinctes dansnums.
Exemples
- Entrée
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- Sortie
- [4, 1]
- Explication
4apparaît quatre fois,1trois fois, et2et3une fois chacun. Les deux valeurs les plus fréquentes sont4, puis1.
- Entrée
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- Sortie
- [-2, 5]
- Explication
-2,5et7apparaissent chacun deux fois et9une fois. Trois valeurs sont à égalité en tête, donc les deux plus petites,-2et5, sont la réponse.
- Entrée
- nums = [8]k = 1
- Sortie
- [8]
- Explication
- Il y a une seule valeur, c’est donc la plus fréquente.
+16 tests cachés à la soumission
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Commence par déterminer la fréquence d’apparition de chaque valeur. Quelle structure de données associe une valeur à son nombre d’occurrences en un seul parcours ?
Avec les comptes en main, tu veux les
kmeilleures valeurs selon un ordre : d’abord le compte le plus élevé, puis la plus petite valeur en cas d’égalité. Trier chaque valeur distincte fonctionne. Un tas min de taillekne conserve que les valeurs qui peuvent encore faire partie de la réponse.Un compte est un nombre entier de 1 à
n. Créez un compartiment pour chaque compte, le compartimentccontenant les valeurs qui apparaissent exactementcfois, puis parcourez les compartiments du compte le plus élevé au plus faible. Remplissez les compartiments en parcourant les valeurs de la plus petite à la plus grande, et chaque compartiment est déjà dans l’ordre de départage.
Solution
Le comptage est la partie rapide : un seul passage avec une table de hachage donne le nombre d’occurrences de chaque valeur. La vraie question est de savoir comment choisir les k meilleures valeurs sans effectuer plus de travail que nécessaire. Trier les d valeurs distinctes par nombre d’occurrences coûte O(d log d), un tas min de taille k ramène ce coût à O(d log k), et comme un nombre d’occurrences est un entier compris entre 1 et n, un tri par cases ordonne les valeurs selon leur nombre d’occurrences sans aucune comparaison.
Compter, puis trier par nombre
Intuition
Commence par compter. Un seul passage avec une table de hachage associant chaque valeur à son nombre d’occurrences transforme [4, 1, 4, 2, 1, 4, 3, 1, 4] en 4 → 4, 1 → 3, 2 → 1, 3 → 1.
Place ensuite les valeurs distinctes dans l’ordre de la réponse : le nombre d’occurrences le plus élevé en premier, et, à nombre égal, la plus petite valeur en premier. Indique exactement cette comparaison pour le tri : le nombre d’occurrences comme premier critère et la valeur comme second. Les k premiers éléments de la liste triée constituent la réponse. Ici, l’ordre est 4, 1, 2, 3, et k = 2 retient 4 et 1.
Le comptage coûte O(n). Le tri des d valeurs distinctes coûte O(d log d), soit au plus O(n log n) lorsque toutes les valeurs sont différentes : 10^4 valeurs nécessitent environ 1.3 × 10^5 comparaisons, ce qui est rapide. Le gaspillage vient du fait que le tri ordonne toutes les valeurs alors que seules les k premières comptent.
Algorithme
- Comptez chaque valeur dans une table de hachage.
- Placez les valeurs distinctes dans une liste.
- Triez la liste par nombre d’occurrences décroissant, puis par valeur croissante lorsque les nombres d’occurrences sont égaux.
- Renvoyez les
kpremières valeurs.
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]Conservez les k meilleurs éléments dans un tas min
Intuition
Tu n’as besoin que des k meilleures valeurs, alors ne conserve que k candidates. Pour chaque nouvelle valeur, la question est de savoir si elle surpasse la candidate la plus faible que tu conserves, où « plus faible » signifie un compte inférieur, ou le même compte et une valeur plus grande. Un tas min ordonné selon cette règle garde la candidate la plus faible au sommet, où tu peux la consulter en O(1) et la remplacer en O(log k).
Parcours les valeurs distinctes. Tant que le tas contient moins de k valeurs, ajoute la valeur. Ensuite, une valeur qui surpasse celle au sommet la remplace, et une valeur qui ne la surpasse pas est écartée, car k meilleures valeurs sont déjà conservées. Avec un tas fourni par une bibliothèque, il est plus court d’ajouter chaque valeur, puis d’en retirer une dès que le tas dépasse k, ce qui conserve les mêmes k valeurs.
À la fin, le tas contient la réponse, mais pas dans l’ordre attendu : un tas n’est que partiellement trié. Le retrait renvoie d’abord la valeur la plus faible ; écris donc la réponse en commençant par la dernière position et en remontant jusqu’à la première.
Chacune des d valeurs distinctes nécessite au plus une opération sur le tas contenant k éléments, donc la sélection prend O(d log k). C’est plus rapide que le tri lorsque k est bien inférieur à d, par exemple pour trouver les 10 premières parmi 8000 valeurs distinctes.
Algorithme
- Comptez chaque valeur dans une table de hachage.
- Pour chaque valeur distincte, insérez-la tant que le tas contient moins de
kvaleurs. - Une fois que le tas est plein, comparez la valeur à celle au sommet, la plus faible valeur conservée. Si la nouvelle valeur est plus grande, placez-la au sommet et faites-la descendre dans le tas.
- Retirez les éléments du tas
kfois, en écrivant chaque valeur dans la réponse de la dernière position à la première.
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return resultCompter, puis trier par compartiments selon la fréquence
Intuition
Un décompte n’est pas n’importe quel nombre : c’est un entier compris entre 1 et n. Cela permet d’utiliser un tri par compartiments. Créez un compartiment par décompte, le compartiment c contenant les valeurs qui apparaissent exactement c fois, puis parcourez les compartiments en partant du compartiment n. Les valeurs sortent de la plus fréquente à la moins fréquente, et aucun décompte n’est jamais comparé à un autre.
La règle de départage impose une chose de plus : dans un compartiment, la plus petite valeur doit venir en premier. Les valeurs sont comprises entre -10^4 et 10^4, donc un tableau de R = 2 × 10^4 + 1 compteurs suffit pour les compter, avec la valeur v à l’indice v + 10^4. Parcourez ce tableau de la plus petite valeur à la plus grande et ajoutez chaque valeur au compartiment correspondant à son décompte. Chaque compartiment se remplit par ordre croissant, ce qui respecte l’ordre de départage ; aucun tri n’est donc nécessaire.
Pour [5, -2, 7, -2, 7, 5, 9], le parcours place -2, 5, 7 dans le compartiment 2, dans cet ordre, et 9 dans le compartiment 1. En parcourant les compartiments à partir du compartiment 7, le premier compartiment contenant des valeurs est le compartiment 2, et k = 2 prend -2 et 5.
Le travail consiste en un parcours de nums, un parcours des R compteurs et un parcours des compartiments, soit O(n + R) au total : une complexité linéaire pour une plage de valeurs fixe. Avec une table de hachage à la place du tableau de comptage, le décompte reste linéaire, mais les compartiments se remplissent dans l’ordre de la table, et il faudrait trier chacun d’eux pour respecter la règle de départage.
Algorithme
- Comptez chaque valeur dans un tableau indexé par
value + 10^4. - Créez des compartiments de 1 à
n, une liste par nombre d’occurrences possible. - Parcourez le tableau de comptage de la plus petite valeur à la plus grande, et ajoutez chaque valeur présente au compartiment correspondant à son nombre d’occurrences.
- Parcourez les compartiments du nombre d’occurrences
njusqu’à 1, en prenant des valeurs jusqu’à en avoirk.
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
Pièges et cas limites
Le comptage est rarement erroné. C’est l’ordre de la réponse qui pose problème.
- Départager les égalités selon l’ordre de première apparition ou l’ordre de la table de hachage. Dans le deuxième exemple,
-2,5et7apparaissent tous deux fois, et seule la règle de la plus petite valeur fait de[-2, 5]la bonne réponse. - Renvoyer le tableau du tas tel quel. Un tas n’est que partiellement ordonné, et son sommet est la valeur la plus faible, celle qui doit venir en dernier.
- Inverser la règle de départage du tas. Parmi deux valeurs ayant le même compte, la plus grande est la plus faible ; un tas min sur
(count, value)élimine donc la mauvaise. Utilisez(count, -value)ou une comparaison définie selon la règle. - Créer seulement autant de compartiments qu’il y a de valeurs distinctes. Une valeur peut apparaître
nfois, comme dans[3, 3, 3, 3]: le compartimentndoit donc exister. - En Java, comparer deux comptes
Integeravec!=. Cela compare les références et pose problème dès que les comptes dépassent 127. Convertissez-les d’abord enint. - Prendre tout un compartiment à la fin. Arrêtez-vous dès que vous avez
kvaleurs, même au milieu d’un compartiment.
Questions fréquentes4
Quelle est la complexité temporelle de Top K Frequent Elements ?
Le comptage prend O(n). La sélection des k premiers éléments coûte ensuite O(d log d) avec un tri des d valeurs distinctes, O(d log k) avec un tas min de taille k, et O(n) plus un parcours de l’intervalle des valeurs avec le tri par compartiments. Comme d peut atteindre n, le tri est en O(n log n) dans le pire des cas et le tri par compartiments est linéaire.
Peut-on résoudre le problème des K éléments les plus fréquents en temps O(n) ?
Oui, avec le tri par compartiments. Les comptes sont des nombres entiers de 1 à n, donc chaque valeur va dans le compartiment correspondant à son compte, et lire les compartiments du compte le plus élevé au plus faible classe les valeurs par fréquence sans aucun tri par comparaison. La sélection rapide sur les comptes est également en O(n) en moyenne, mais son pire cas est quadratique.
Pourquoi utiliser un tas min et non un tas max ?
Un tas max de toutes les valeurs d convient aussi : on le construit en O(d), puis on effectue k extractions, soit O(d + k log d) au total. Un tas min de taille k ne contient que k entrées et convient aux valeurs qui arrivent une par une, car son sommet est le candidat à supprimer. En contrepartie, il renvoie le résultat à l’envers, donc on remplit le résultat en partant de la fin.
Comment départager les ex æquo dans Top K Frequent Elements ?
Choisissez une règle et appliquez-la partout ; ici, en cas d’égalité des comptes, la plus petite valeur vient en premier, ce qui rend la réponse unique. Dans un tri, comparez les comptes, puis les valeurs. Dans un tas, parmi deux comptes égaux, la plus grande valeur est la moins prioritaire. Dans un tri par compartiments, remplissez les compartiments par ordre croissant de valeur, et chaque compartiment respecte déjà l’ordre en cas d’égalité.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def topKFrequent(nums, k):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
Attendu
[4, 1]