347. Top K Frequent Elements

Sommaire

Description

Approche

Réflexions clés

Erreurs commises à éviter

Rectifications

Solution finale

En savoir plus sur la série Arrays and Hashing

Description

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Étant donné un tableau d'entiers nums et un entier k, retourner les k éléments les plus fréquents. Vous pouvez retourner la réponse dans n'importe quel ordre.

Approche

On veut débuter la résolution de ce problème avec une dictionnaire pour compter les occurrences des valeurs de la liste. Ensuite, récupérer les k nombres d’occurrences les plus grandes de la liste des valeurs du dictionnaire. Et enfin, récupérer les clés correspondantes à ces valeurs.

Réflexions clés

• Notre première approche était bonne. En utilisant des sets, notre code fait de bonnes performances en terme de complexité mémoire mais est beaucoup moins bon en terme de complexité temps.

• Je viens de me rendre compte que Neetcode propose des solutions sous forme vidéo en plus du code. Je vais donc reprendre tous les problèmes que j’ai résolu jusque là et rajouter dans mes réflexions, les choses que j’ai apprises. Après submission, la solution de Neetcode a été excellente en Runtime en battant 76.90% des codes Python, et est légèrement moins bon en Memory en battant seulement 25.44 % des codes Python.

  • À retenir :

    • Max Heap :

    • Bucket sort : utilise un tableau avec le nombre comme index

    • Hash Map : pour compter les occurrences du tableau d'entrée

• L’implémentation la plus efficace en Runtime est la suivante avec 28 ms :

• L’implémentation la plus efficace en Memory est la suivante avec 18.9 MB :

Erreurs commises à éviter

• Bien se familiariser avec les spécificités des structures de données pour savoir laquelle utiliser et éviter les erreurs de duplication, de redondances etc.

Rectifications

RAS

Solution finale

En savoir plus sur la série Arrays and Hashing

Cet article touche à sa fin, mais notre exploration des Arrays et Hashing ne fait que commencer. Ne manquez pas nos autres articles de la série pour approfondir vos connaissances, surtout si vous débutez ! Apprenez de mes expériences et progressez avec nous.