查找连续中位数

Question

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

1 - 平均为1 1,2 - 平均为3/2 1,2,3 - 平均是2

Answer 1

您可以在每个元素的O（logn）中执行此操作。

构建AVL树（或RBT），将一个指针设置为中值。现在用完全线程（两者），父指针来扩充AVL。
插入时间是对数，后继和前任是恒定操作，因此更新中值指针是恒定时间操作。

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

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

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

Answer 2

我看不出它可以在更短时间内完成为O （n）时间。

您将不得不保留一个目前项目的排序列表。每当有新物品到达时，您必须将其插入正确的位置。这将需要O（n）时间。

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