Tri par fréquence avec conservation de l'ordre

Swift Hard sorting

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

Étant donné un tableau d'entiers. Triez-le par ordre décroissant de la fréquence d'apparition des éléments. Si deux éléments ont la même fréquence, ils doivent être placés dans l'ordre de leur première apparition dans le tableau d'origine. Implémentez un algorithme avec une complexité temporelle de O(n log n) et n'utilisez pas de fonctions de tri intégrées avec des comparateurs personnalisés.

Format d\ entrée

La première ligne contient un entier n (1 ≤ n ≤ 10^5) — le nombre d'éléments. 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

4
1 2 2 3

SORTIE

2 2 1 3

Exemple 2

ENTRÉE

6
1 2 3 4 5 6

SORTIE

1 2 3 4 5 6

Exemple 3

ENTRÉE

1
7

SORTIE

7

main.swift