online algorithm 找中位數

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