排序N元素的数组与O（LOGN）不同的元素在O（nloglogn）最坏情况下的时间 [英] Sorting an n element array with O(logn) distinct elements in O(nloglogn) worst case time

问题描述

眼下的问题是什么在标题本身。这是给一个算法进行排序在O（nloglogn）最坏情况下的n元素的数组与O（LOGN）不同的元素。任何想法？

The problem at hand is whats in the title itself. That is to give an algorithm which sorts an n element array with O(logn) distinct elements in O(nloglogn) worst case time. Any ideas?

另外，你如何处理一般的阵列与多个非重复元素？

Further how do you generally handle arrays with multiple non distinct elements?

推荐答案

O（日志（LOG（ N 的）））时间足够让你做一个基本操作为O搜索树（日志（ N 的））的元素。

O(log(log(n))) time is enough for you to do a primitive operation in a search tree with O(log(n)) elements.

因此​​，保持所有的不同的的，你所看到的，到目前为止元素平衡查找树。树中的每个节点还含有你已经看到与该键的所有元素的列表。

Thus, maintain a balanced search tree of all the distinct elements you have seen so far. Each node in the tree additionally contains a list of all elements you have seen with that key.

漫步输入元素一个接一个。对于每个元素，试图将其插入树（这需要O（log日志的 N 的）时间）。如果你发现你已经看到相同的元素，只是将其插入辅助列表中已经存在的节点。

Walk through the input elements one by one. For each element, try to insert it into the tree (which takes O(log log n) time). If you find you've already seen an equal element, just insert it into the auxiliary list in the already-existing node.

遍历整个列表之后，穿行于树顺序串联辅助列表。 （如果你照顾在恰当的两端辅助列表插入，这甚至是一个稳定的排序）。

After traversing the entire list, walk through the tree in order, concatenating the auxiliary lists. (If you take care to insert in the auxiliary lists at the right ends, this is even a stable sort).

这篇关于排序N元素的数组与O（LOGN）不同的元素在O（nloglogn）最坏情况下的时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！