Nombre d'occurrences dans un tableau en O (n log n) temps

Question

Étant donné un tableau non trié, A[], contenant n entiers, comment créer un algorithme pour renvoyer l'élément qui s'est produit le plus souvent?

Je suppose que vous auriez besoin d'un moyen de compter le nombre de fois qu'un élément se produit. Je peux seulement comprendre une implémentation O (n). Je sais que je dois d'abord utiliser un algorithme de tri, mais si je devais utiliser le tri par fusion, c'est déjà l'exécution totale de O (n logn)). J'ai seulement trié les données et je ne peux pas regarder les éléments sans augmenter encore le temps d'exécution.

Answer 1

Triez le tableau, puis tous les éléments récurrents sont côte à côte.
parcourons simplement le tableau, tout en maintenant un maxSeen et currSeen compteurs, si l'élément courant est égal dernier élément, augmenter currSeen, sinon - Remise à zéro currSeen et remplacer maxSeen si le currSeen est plus grand que lui.

Le tri est O (n log n), et une fois itérer est O (n), donc au total O(nlogn + n) = O(nlogn)

Il est des devoirs, donc suivant ces directives pour créer un code devrait être votre tâche. Bonne chance!

---

Comme une note de côté, puisque c'est au moins aussi fort que Element Distinctness Problem et it cannot be done better than O(nlogn) à l'aide de comparaisons des algorithmes basés.

---

Side note deux, il peut être fait en temps O(n) + espace en utilisant des tables-hachage.
Créez un histogramme des données, qui est un hachage, dans lequel une clé est un élément, et la valeur est le nombre d'occurrences. Ensuite, le problème se résout à trouver la valeur maximale dans cette table de hachage.
La construction de la table est O(n) en moyenne, et le maximum est O(n).

Ceci utilise cependant O(n) de mémoire supplémentaire, et pourrait se détériorer jusqu'à O(n^2) dans le pire des cas.

Answer 2

Vous supposez que c'est une bonne idée de commencer par trier le tableau. Cela coûte O (n log n), comme vous le faites remarquer. Ensuite, vous pouvez analyser le tableau et calculer la fréquence de chaque valeur un par un, en vous souvenant de la valeur la plus fréquente au fur et à mesure. Cela coûte O (n). Le coût total est O (n log n + n), qui est O (n log n). Pour savoir pourquoi, considérons O (2n log n). Ceci est sûrement dans O (n log n) parce que 2n log n est dans un facteur constant de n log n. Et n log n + n est délimité ci-dessus par 2n log n, donc il est également dans O (n log n).