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