Hello 👋
Cette semaine on se retrouve pour un problème de string processing et de priority queue, le 692. Top K Frequent Words.
L’énoncé
Soit une liste non vide de mots, retournez les k mots les plus fréquents de cette liste.
Le résultat est attendu sous forme de liste de mots triée par ordre décroissant de fréquence d’apparition. Si deux mots ont la même fréquence, le mot le plus petit dans l’ordre lexicographique apparaît le premier.
Piste de résolution
La formulation en top-k éléments fait sonner la cloche priority queue / heap 🔔
💡 Une heap est une structure de données optimisée pour accéder au plus petit (min heap) ou plus grand élément (max heap) d’une collection avec un coût en O(1)
. L’insertion d’un élément se fait en O(log(n))
runtime avec n le nombre d’éléments de la heap.
1️⃣ Avant d’avoir cette liste de priorités, nous avons besoin d’avoir les différents mots à insérer ainsi que leurs priorités (ici, leurs fréquences).
Pour cela, on peut utiliser une hash table - dictionnaire en python. On parcourt la liste des mots et incrémente l’entrée associée du dictionnaire pour chaque mot.
Encore mieux! La librairie standard collections propose la classe Counter
dont l’objectif est spécifiquement de compter des éléments hashables, parfait pour compter nos mots!
2️⃣ Nous disposons donc d’une liste d’éléments avec leur « priorité » (l’occurrence de chaque mot dans la liste des mots)
On peut donc en créer une max heap.
Une proposition d’implémentation en Python :
from collections import Counter | |
import heapq | |
from typing import List | |
class Solution: | |
def topKFrequent(self, words: List[str], k: int) -> List[str]: | |
""" | |
https://leetcode.com/problems/top-k-frequent-words | |
Args: | |
words: List[str] | |
k: int | |
Returns: | |
List[str] of the k most frequent word in words | |
""" | |
count = Counter(words) # O(n) runtime, O(n) space | |
heap = (heapq.nsmallest(k, count.items(), key=lambda item: (-item[1], item[0]))) # O(n*log[k]) runtime, O(n) space | |
return [word for word, _ in heap] # O(k) runtime, O(k) space |
Solution inspirée de ce commentaire leetcode
On insère n paires (-occurrence, mot) dans cette heap de taille k pour un coût asymptotique en runtime de O(n*log[k])
.
La clé de tri prend deux arguments, le premier pour les occurences, le second pour s’assurer le respect de l’ordre lexicographique en cas d’égalité sur la valeur de la première clé de tri 🔑
💡 Le coût d’insertion d’un élément dans une heap de k éléments est O(log(k))
.
Le signe moins devant occurrence est important car il nous permet de créer une max heap (par défaut min heap dans le module heapq
).
On récupère ensuite les k plus grands éléments avec la fonction nsmallest
de heapq.
Note: Les k plus grands éléments correspondent ici aux k nombres négatifs les plus petits 😉
Le walkthrough détaillé de cette solution est aussi disponible ici 👇
Samedi prochain ~ Focus sur les trees 🌲
La semaine prochaine, on se retrouve pour un problème sur les arbres le 236 - Lowest Common Ancestor of a Binary Tree 🔗.
A samedi prochain! As usual, 09:30am Paris time sur notre Twitch LeetGrindFr 😉
See ya,
Your friends at Leetgrind,
Photo de thumbnail de Olha Ruskykh