手头的问题是标题本身的问题.这是给出一种算法,该算法在O(nloglogn)最坏情况时间内对具有O(logn)不同元素的n元素阵列进行排序.有任何想法吗？
进一步如何处理具有多个非不同元素的数组？
Hen*_*olm 11
O(log(log(n)))时间足以让您在具有O(log(n))元素的搜索树中执行原始操作.
因此,维护一个平衡的搜索树,其中包含您目前所见的所有不同元素.树中的每个节点还包含您使用该键看到的所有元素的列表.
逐个浏览输入元素.对于每个元素,尝试将其插入树中(需要O(log log n)时间).如果您发现已经看到了相同的元素,只需将其插入已存在节点的辅助列表中即可.
遍历整个列表后,按顺序遍历树,连接辅助列表.(如果注意在右端插入辅助列表,这甚至是一种稳定的排序).