Top K Frequent Elements

Description

[EN]

Given an integer array nums and an integer k, return the k most frequent elements within the array. The test cases are generated such that the answer is always unique. You may return the output in any order.

Constraints:

• 1 <= nums.length <= 10^4.

• -1000 <= nums[i] <= 1000

• 1 <= k <= number of distinct elements in nums.

[FR]

Étant donné un tableau d'entiers nums et un entier k, retournez les k éléments les plus fréquents dans le tableau. Les cas de test sont générés de manière à garantir que la réponse est toujours unique. Vous pouvez retourner le résultat dans n'importe quel ordre.

Contraintes :

• 1 <= nums.length <= 10^4 : Le tableau nums contient entre 1 et 10 000 éléments.

• -1000 <= nums[i] <= 1000 : Chaque élément du tableau est compris entre -1000 et 1000.

• 1 <= k <= nombre d'éléments distincts dans nums : La valeur de k est toujours inférieure ou égale au nombre d'éléments distincts dans nums.

Approche: Utilisation d'une HashMap et d'une variante du tri par paquets

• Pour résoudre ce problème, on crée d'abord une HashMap<Integer, Integer>:

  • La clé désigne un entier présent dans le tableau

  • La valeur désigne le nombre de fois que l'entier est présent dans le tableau

• On effectue un parcours du tableau nums:

  • Si l'entier actuel n'a pas encore été rencontré, on initialise la clé dans la HashMap, et la valeur à 1

  • Sinon, on met à jour la valeur associée à l'entier.

• On crée ensuite un tableau freq contenant des listes d'entiers:

  • L'indice représente le nombre de fois qu'une valeur est présente dans le tableau num

  • A chaque case du tableau, on a une liste d'entiers. Chaque liste contient tous les entiers présents dans le tableau exactement un nombre de fois correspondant à l'indice.

  • Ce tableau a pour taille nums.length + 1. Cela est du au fait que l'on ne pourra jamais avoir une valeur présente dans le tableau un plus grand nombre de fois que la taille du tableau lui même.

• On initialise notre tableau

• On itère notre HashMap:

  • Pour chaque paire <clé, valeur> de la HashMap, on ajoute dans notre tableau à la liste présente à l'indice valeur, le nombre clé

• On crée ensuite notre tableau res contenant le résultat

• On itère notre tableau freq de la fin vers le début:

  • On ajoute les entiers rencontrés jusqu'à ce qu'on ait atteint la limite, c'est à dire k.

  • Dès que l'on a ajouté k nombres au résultat, on le retourne immédiatement.

• Complexité temporelle: O(n) 

• Complexité spatiale: O(n) car utilisation d'une HashMap et d'un tableau