Tri par fréquence avec conservation de l’ordre

Rust Hard sorting

Tâche «Tri par fréquence avec conservation de l’ordre»

Étant donné un tableau d’entiers. Il faut le trier par ordre décroissant de la fréquence d’apparition des éléments. Si deux éléments apparaissent le même nombre de fois, ils doivent être placés dans l’ordre de leur première apparition dans le tableau initial. Il est nécessaire d’implémenter un algorithme de tri avec une complexité temporelle O(n log n) et une utilisation de mémoire supplémentaire O(n).

Format d\ entrée

La première ligne contient un entier n (1 ≤ n ≤ 10^5). La deuxième ligne contient n entiers séparés par des espaces.

Format de sortie

Affichez n entiers séparés par des espaces — le tableau trié.

Exemples

Exemple 1

ENTRÉE

3
3 2 1

SORTIE

3 2 1

main.rs