arrays - 数组中不同整数的数量是 O(log n)。如何获得 O(n log log n) 最坏情况时间算法来对此类序列进行排序？

Question

问题来自算法设计手册。我一直在研究它，但还没有找到得出正确答案的方法。

问题:我们寻求对具有许多重复项的 n 个整数序列 S 进行排序，使得 S 中不同整数的数量为 O(log n)。给出一个 O(n log log n) 最坏情况时间算法来对这样的序列进行排序。

我想也许可以先挑选所有这些不同的元素并形成一个 logn 长度的数组，然后记录频率并对其进行排序。然而，我的第一步似乎使运行时间过长......是否有更好的选择方法或者我的方法完全错误？谢谢

Answer 1

用平衡二叉树计算每个数字出现的次数。由于只有 log N 个不同的数字，树的大小为 log N，因此所有操作都在 log log N 中执行。(这正是 map<> 在 C++ 中的实现方式)

然后，只需按预序遍历迭代树的节点，并按此顺序打印每个整数所需的次数。