查找連續中位數

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。