online algorithm 找中位數

[sorryChen (陳揚和)]

這是個面試問題..但我也不知道解答


給定一個一直會產生的數列..要如何最有效率的找到中位數
如果是要求平均只要constant time 和 space, 中位數就得要所有數都存了
(因為任何過去出現的數都有可能在新產生幾個數列後變成中位數)

如果固定n個數, 需要O(n)的時間和空間可以找到第k大的數(任意k)
(selection), 但如果這個數列一直在產生呢?
有沒有data structure 可以在n個數後新加m個數,而能在O(m)找到中位數?

O(mlogn)倒是應該可以(不太確定)
若有個blance binary search tree, 並且計有每個子樹下有多少個數,
中位數應該離root不遠, 可能可以在有這樣的數中constant time找到
(對嗎?) 新插入m個數也只要mlogn

實際問題若資料有特殊的分佈也許也可以把數分堆

不知道版上有沒有大師可以指導解惑


--
Life is continuous

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 108.94.138.88
推 EdisonX:轉去 Prob_Solve 應較佳。
→ EdisonX:補一下,我也不知道正解,但我會用 bucket.
推 rifiz:用兩個heap, 一個max 一個min 就可以達到
※ sorryChen:轉錄至看板 Prob_Solve                                 08/18 00:20
→ sorryChen:兩個heap如何能有效的找中位數呢?
→ sorryChen:話說有個DS叫MinMaxHeap,但無關中位數
推 JingXD:疑.. 不是online看新還的比現在有中位數
→ cathat:把所有的數字依大小分兩半
→ cathat:minHeap 存大的那一半的最小的一個
→ cathat:maxHeap 存小的大一半最大的那一個
→ cathat:median 可以從這兩個數字推出來
推 Huangs:如樓上說狦兩個heap，而且用fibonacci heap
→ Huangs:fibonacci heap的insert/find分攤都是O(1)
推 Huangs:兩個heap 一個存大的一半 一個存小的一半
→ Huangs:然後一直保持兩個heap一樣大
→ Huangs:中位數就在兩個heap的root。
→ BombCat:可是如果能依大小分兩半那就表示已經知道
→ BombCat:中位數了?
→ Arton0306:不過還要delete, fib heap是lnN
推 suhorng:大小是固定一半一半的 一開始只有一個元
→ suhorng:素當然沒問題 以後每次加入新的都要維持
→ suhorng:兩邊元素個數差不多
→ sorryChen:感謝給位大師及Prob_Solve有版友賜教
→ sorryChen:所以這個問題應該只有O(mlnN)的解法
→ sorryChen:m是隨後新加入的元素
推 singlovesong:應該沒有linear解法
→ singlovesong:每進來一個新值 勢必會動到舊的
→ singlovesong:資料 沒有辦法在O(1)插入新值
→ singlovesong:且還保持資結sorted的狀態
推 Huangs:沒有刪除的話，是可以linear的。
推 singlovesong:請問要怎麼做@@?
推 Huangs:就是前面講的，fibonacci heap
→ Huangs:的insert/find都是 O(1) (amortized)
推 Huangs:我想起來還是要delete才能維持兩heap平衡
→ Huangs:果然還是沒辦法 @@
推 yoco315:嗯,難的就是平衡的時候要用掉lnN :(