作者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