median - 寻找连续中位数

Question

您将如何计算每次添加新输入时都会更新的给定输入的中位数？例如：

• 1 - 中位数为 1
• 1,2 - 中位数为 3/2
• 1,2,3 - 中位数为 2

Answer 1

我看不出它是如何在少于 O(n) 的时间内完成的。

您将必须保留现有项目的排序列表。每当有新物品到达时，您都必须将其插入正确的位置。这将需要 O(n) 时间。

计算新的中位数是基本的。如果新的 N 是奇数，那么它是 array[(N-1)/2]，否则它是 (array[(N)/2] + array[(N)/2 - 1]) / 2。

Answer 2

您可以在每个元素的 O(logn) 中完成此操作。

建立 AVL 树（或 RBT），设置一个指针指向中值。现在用全线程（两者）、父指针来增加 AVL。
插入时间是对数的，后继和前驱是常数操作，因此更新中位指针是常数时间操作。

父指针加线程可能看起来是多余的，但这保证不会遍历，中值更新是在旋转阶段完成的。

优点：只有插入时间很重要。结构是动态的，无需重新分配数组或移动元素。

缺点：空间和分配节点存在开销。