我在一次采访中遇到了一个有趣的算法问题.我给出了答案,但不确定是否有更好的主意.所以我欢迎大家写一些他/她的想法.
你有一个空集.现在元素逐个放入集合中.我们假设所有元素都是整数,它们是不同的(根据集合的定义,我们不考虑具有相同值的两个元素).
每次将新元素添加到集合中时,都会询问集合的中值.中值定义与数学中的相同:排序列表中的中间元素.这里,特别地,当集合的大小是偶数时,假设set = 2*x的大小,中值元素是集合的第x个元素.
一个例子:从空集开始,当添加12时,中位数为12,当添加7时,中位数为7,当添加8时,中位数为8,当添加11时,中位数为8,当添加5,中位数为8,当加16时,中位数为8,...
请注意,首先,元素被添加到逐个设置,其次,我们不知道要添加的元素.
我的答案.
由于这是一个关于寻找中位数的问题,因此需要进行排序.最简单的解决方案是使用普通数组并保持数组排序.当新元素到来时,使用二进制搜索来查找元素的位置(log_n)并将元素添加到数组中.由于它是一个普通的数组,因此需要移动阵列的其余部分,其时间复杂度为n.插入元素后,我们可以使用实例时间立即获得中位数.
最糟糕的时间复杂度是:log_n + n + 1.
另一种解决方案是使用链接列表.使用链接列表的原因是消除了移动阵列的需要.但是找到新元素的位置需要线性搜索.添加元素需要立即时间,然后我们需要通过遍历数组的一半来找到中值,这总是需要n/2次.
最差时间复杂度为:n + 1 + n/2.
第三种解决方案是使用二叉搜索树.使用树,我们避免移动数组.但是使用二叉搜索树来查找中位数并不是很有吸引力.所以我改变二叉搜索树的方式总是左子树和右子树是平衡的.这意味着在任何时候,左子树和右子树都具有相同数量的节点,或者右子树比左子树中的节点多一个节点.换句话说,确保在任何时候,根元素是中值.当然,这需要改变树的构建方式.技术细节类似于旋转红黑树.
如果树被正确维护,则确保WORST时间复杂度为O(n).
因此,这三种算法都与集合的大小成线性关系.如果不存在子线性算法,则可以将这三种算法视为最优解.由于它们彼此之间没有太大区别,因此最好的是使用链接列表最容易实现,这是第二个.
所以我真的很想知道,这个问题是否会有一个亚线性算法,如果是这样的话会是什么样的.有什么想法吗？
史蒂夫.
Jon*_*ehl 23
您的复杂性分析令人困惑.假设添加了n个项目; 我们希望有效地输出n个中间流(其中流中的第i个是前i个项的中值).
我相信这可以使用两个优先级队列(例如二进制或斐波那契堆)在O(n*lg n)时间内完成; 当前中位数以下项目的一个队列(所以最大元素位于顶部),另一个队列位于其上方(在此堆中,最小值位于底部).注意,在fibonacci(和其他)堆中,插入是O(1)摊销; 它只弹出一个O(lg n)的元素.
这将被称为"在线中位数选择"算法,尽管维基百科仅讨论在线最小/最大选择.这里有一个近似算法和下界确定性和近似在线位数选择(下限手段没有更快的算法是可能的!)
如果与n相比存在少量可能的值,则可能会破坏基于比较的下限,就像您可以进行排序一样.
Lar*_*erg 10
我收到了同样的面试问题,并在争吵的帖子中提出了两堆解决方案.正如他所说,每次操作的时间是O(log n)最坏情况.该预期时间也是O(log n)的,因为你要"流行元素"的假设随机输入的时间的1/4.
我随后进一步思考并找出了如何获得恒定的预期时间; 实际上,每个元素的预期比较数变为2 + o(1).你可以在http://denenberg.com/omf.pdf上看到我的写作.
顺便说一句,这里讨论的解决方案都需要空间O(n),因为你必须保存所有元素.一种完全不同的方法,只需要O(log n)空间,可以得到中位数的近似值(不是精确的中位数).对不起,我无法发布链接(每个帖子我只限一个链接),但我的论文有指针.
虽然已经回答了争吵,但我希望描述一种亚线性搜索树方法的修改.
我们现在可以使用以下计数访问O(log n)中的Kth最小元素:
def get_kth_item(subtree, k):
left_size = 0 if subtree.left is None else subtree.left.size
if k < left_size:
return get_kth_item(subtree.left, k)
elif k == left_size:
return subtree.value
else: # k > left_size
return get_kth_item(subtree.right, k-1-left_size)
中位数是Kth最小元素的特例(假设你知道集合的大小).
总而言之,这是另一个O(log n)解决方案.