Sortierung nach Häufigkeit unter Beibehaltung der Reihenfolge

Swift Hard sorting

Aufgabe «Sortierung nach Häufigkeit unter Beibehaltung der Reihenfolge»

Gegeben ist ein Array ganzer Zahlen. Sortieren Sie es absteigend nach der Häufigkeit des Vorkommens der Elemente. Wenn zwei Elemente die gleiche Häufigkeit haben, dann sollen sie in der Reihenfolge ihres ersten Auftretens im ursprünglichen Array angeordnet werden. Implementieren Sie einen Algorithmus mit einer Zeitkomplexität von O(n log n) und verwenden Sie keine integrierten Sortierfunktionen mit benutzerdefinierten Vergleichsfunktionen.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl n (1 ≤ n ≤ 10^5) — die Anzahl der Elemente. Die zweite Zeile enthält n ganze Zahlen, getrennt durch Leerzeichen.

Ausgabeformat

Geben Sie n ganze Zahlen, getrennt durch Leerzeichen, aus — das sortierte Array.

Beispiele

Beispiel 1

EINGABE

4
1 2 2 3

AUSGABE

2 2 1 3

Beispiel 2

EINGABE

6
1 2 3 4 5 6

AUSGABE

1 2 3 4 5 6

Beispiel 3

EINGABE

1
7

AUSGABE

7

main.swift