作者sorryChen (陳揚和)
看板Prob_Solve
標題Fw: online algorithm 找中位數
時間Sat Aug 18 00:20:43 2012
※ [本文轉錄自 Programming 看板 #1GBUF2_m ]
作者: 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
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: sorryChen (108.94.138.88), 時間: 08/18/2012 00:20:43