Fw: online algorithm 找中位數

看板Prob_Solve作者sorryChen (陳揚和)時間12年前 (2012/08/18 00:20)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/3 (看更多)

※ [本文轉錄自 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

推

EdisonX

08/17 16:17, , 1^F

08/17 16:17, 1^F

→

EdisonX

08/17 16:24, , 2^F

08/17 16:24, 2^F

推

rifiz

08/17 17:33, , 3^F

08/17 17:33, 3^F