按频率排序并保持顺序

Rust Hard sorting

任务 «按频率排序并保持顺序»

给定一个整数数组。需要按照元素出现频率的降序对其进行排序。如果两个元素出现的次数相同，则它们应按照在原始数组中首次出现的顺序排列。要求实现时间复杂度为 O(n log n) 且使用额外空间 O(n) 的排序算法。

第一行包含一个整数 n (1 ≤ n ≤ 10^5)。第二行包含 n 个由空格分隔的整数。

输出 n 个以空格分隔的整数——排序后的数组。

输入

3
3 2 1

输出

3 2 1

main.rs