作者sorryChen (陳揚和)
看板Programming
標題online algorithm 找中位數
時間Fri Aug 17 14:25:04 2012
這是個面試問題..但我也不知道解答
給定一個一直會產生的數列..要如何最有效率的找到中位數
如果是要求平均只要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
1F：推 EdisonX:轉去 Prob_Solve 應較佳。 180.177.76.161 08/17 16:17
2F：→ EdisonX:補一下,我也不知道正解,但我會用 bucket. 180.177.76.161 08/17 16:24
3F：推 rifiz:用兩個heap, 一個max 一個min 就可以達到 114.43.191.241 08/17 17:33
※ sorryChen:轉錄至看板 Prob_Solve 08/18 00:20
4F：→ sorryChen:兩個heap如何能有效的找中位數呢? 108.94.138.88 08/18 00:22
5F：→ sorryChen:話說有個DS叫MinMaxHeap,但無關中位數 108.94.138.88 08/18 00:24
6F：推 JingXD:疑.. 不是online看新還的比現在有中位數 203.77.50.240 08/18 01:10
7F：→ cathat:把所有的數字依大小分兩半 128.8.115.58 08/18 03:32
8F：→ cathat:minHeap 存大的那一半的最小的一個 128.8.115.58 08/18 03:32
9F：→ cathat:maxHeap 存小的大一半最大的那一個 128.8.115.58 08/18 03:32
10F：→ cathat:median 可以從這兩個數字推出來 128.8.115.58 08/18 03:34
11F：推 Huangs:如樓上說狦兩個heap，而且用fibonacci heap 118.166.90.91 08/18 04:34
12F：→ Huangs:fibonacci heap的insert/find分攤都是O(1) 118.166.90.91 08/18 04:34
13F：推 Huangs:兩個heap 一個存大的一半 一個存小的一半 118.166.90.91 08/18 04:37
14F：→ Huangs:然後一直保持兩個heap一樣大 118.166.90.91 08/18 04:38
15F：→ Huangs:中位數就在兩個heap的root。 118.166.90.91 08/18 04:38
16F：→ BombCat:可是如果能依大小分兩半那就表示已經知道220.132.195.217 08/18 09:48
17F：→ BombCat:中位數了?220.132.195.217 08/18 09:49
18F：→ Arton0306:不過還要delete, fib heap是lnN 114.42.54.141 08/18 10:52
19F：推 suhorng:大小是固定一半一半的 一開始只有一個元 118.166.56.185 08/18 12:13
20F：→ suhorng:素當然沒問題 以後每次加入新的都要維持 118.166.56.185 08/18 12:13
21F：→ suhorng:兩邊元素個數差不多 118.166.56.185 08/18 12:14
22F：→ sorryChen:感謝給位大師及Prob_Solve有版友賜教 108.94.138.88 08/18 13:07
23F：→ sorryChen:所以這個問題應該只有O(mlnN)的解法 108.94.138.88 08/18 13:08
24F：→ sorryChen:m是隨後新加入的元素 108.94.138.88 08/18 13:09
25F：推 singlovesong:應該沒有linear解法 203.77.50.240 08/18 15:16
26F：→ singlovesong:每進來一個新值 勢必會動到舊的 203.77.50.240 08/18 15:17
27F：→ singlovesong:資料 沒有辦法在O(1)插入新值 203.77.50.240 08/18 15:17
28F：→ singlovesong:且還保持資結sorted的狀態 203.77.50.240 08/18 15:17
29F：推 Huangs:沒有刪除的話，是可以linear的。 118.166.140.98 08/18 23:17
30F：推 singlovesong:請問要怎麼做@@? 203.77.50.240 08/19 10:18
31F：推 Huangs:就是前面講的，fibonacci heap 118.166.140.98 08/19 11:33
32F：→ Huangs:的insert/find都是 O(1) (amortized) 118.166.140.98 08/19 11:33
33F：推 Huangs:我想起來還是要delete才能維持兩heap平衡 118.166.140.98 08/19 11:37
34F：→ Huangs:果然還是沒辦法 @@ 118.166.140.98 08/19 11:37
35F：推 yoco315:嗯,難的就是平衡的時候要用掉lnN :( 219.70.204.108 08/20 07:40