Sortierung nach Häufigkeit mit Beibehaltung der Reihenfolge

Rust Hard sorting

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

Gegeben ist ein Array von ganzen Zahlen. Es muss absteigend nach der Häufigkeit des Vorkommens der Elemente sortiert werden. Wenn zwei Elemente gleich oft vorkommen, sollen sie in der Reihenfolge ihres ersten Auftretens im ursprünglichen Array angeordnet werden. Es ist ein Sortieralgorithmus mit einer Zeitkomplexität von O(n log n) und der Verwendung von zusätzlichem Speicher O(n) zu implementieren.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl n (1 ≤ n ≤ 10^5). 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

3
3 2 1

AUSGABE

3 2 1

main.rs