algorithm - 从不断增长的集合中找出中值

Question

我在面试中遇到了一个有趣的算法问题。我给出了答案，但不确定是否有更好的主意。所以我欢迎大家写点自己的想法。

你有一个空集。现在元素被一个一个地放入集合中。我们假设所有元素都是整数并且它们是不同的(根据集合的定义，我们不考虑具有相同值的两个元素)。

每次向集合中添加新元素时，都会询问集合的中值。中值的定义与数学中的相同:排序列表中的中间元素。这里特别说明一下，当集合的大小为偶数时，假设集合的大小=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。

第三种解决方案是使用二叉搜索树。使用树，我们避免移动数组。但是使用二叉搜索树来寻找中位数并不是很吸引人。所以我改变了二叉搜索树的方式，它总是左子树和右子树是平衡的。这意味着在任何时候，要么左子树和右子树的节点数相同，要么右子树的节点数比左子树多一个。也就是说，保证在任何时候，根元素都是中位数。当然这需要改变树的构建方式。技术细节类似于旋转红黑树。

如果树维护得当，可以保证最坏的时间复杂度为O(n)。

所以这三种算法都与集合的大小成线性关系。如果不存在次线性算法，可以认为三种算法都是最优解。由于它们彼此之间没有太大区别，所以最好的是最容易实现的，这是第二种，使用链接列表。

所以我真正想知道的是，这个问题是否有次线性算法？如果有，它会是什么样子。伙计们有什么想法吗？

史蒂夫。

Answer 1

您的复杂性分析令人困惑。假设总共添加了 n 项；我们想要高效地输出 n 个中位数流(其中第 i 个中位数是前 i 个项目的中位数)。

我相信这可以使用两个优先级队列(例如二进制或斐波那契堆)在 O(n*lg n) 时间内完成；一个队列用于当前中位数以下的项目(因此最大的元素位于顶部)，另一个队列用于其上方的项目(在此堆中，最小的元素位于底部)。请注意，在斐波那契(和其他)堆中，插入是 O(1) 摊销的；它只会弹出一个 O(lg n) 的元素。

尽管Wikipedia，这将被称为“在线中值选择”算法。只谈论在线最小/最大选择。这是一个 approximate algorithm , 和一个 lower bound关于确定性和近似的在线中值选择(下限意味着不可能有更快的算法!)

如果与 n 相比可能的值数量较少，您可以打破基于比较的下限，就像您可以进行排序一样。