r*****e 发帖数: 146 | 1 We have K sorted array, A1, A2, A3,... Ak, the corresponding size for array
Ai is Ni, in total we have N numbers, N = N1 + N2 + ...+Nk. How to find the
median among N numbers in O(K (logN)^2) ? | c********t 发帖数: 5706 | 2 use K min-heap, O(N*log(k))
如果用 quicksort方法,找N/2th 比较复杂,
1 取A1,A2..median元素 A1[N1/2], A2[N2/2]... 存入一个一维数组middle[K];
2 找到middle里的min Ai[Ni/2],
3. change Ai start index = Ni/2+1, 找到新的Ai median,置换掉middle[i];
4. 问题变为找剩下的第N/2 - Ni/2的元素
5. 循环2-4,直到第四步找剩下1个元素,既是middel[k]的min
应该是O(K (logN)^2)
但感觉如果把数组换成一个min-heap存 struct 会得到 O(logK (logN
)^2);
array
the
【在 r*****e 的大作中提到】 : We have K sorted array, A1, A2, A3,... Ak, the corresponding size for array : Ai is Ni, in total we have N numbers, N = N1 + N2 + ...+Nk. How to find the : median among N numbers in O(K (logN)^2) ?
| l*****a 发帖数: 559 | 3 who has the access to acm?
these is a paper on this question.
http://apps.topcoder.com/forums/;jsessionid=8B028A73959B4AF354C | r*****e 发帖数: 146 | 4 不太明白 K(logN)^2中的(logN)^2是怎么出来的。。
第2-4步,可以找middle数组中的最小和最大,将来丢掉比最小小的,比最大大的。
logN)^2);
【在 c********t 的大作中提到】 : use K min-heap, O(N*log(k)) : 如果用 quicksort方法,找N/2th 比较复杂, : 1 取A1,A2..median元素 A1[N1/2], A2[N2/2]... 存入一个一维数组middle[K]; : 2 找到middle里的min Ai[Ni/2], : 3. change Ai start index = Ni/2+1, 找到新的Ai median,置换掉middle[i]; : 4. 问题变为找剩下的第N/2 - Ni/2的元素 : 5. 循环2-4,直到第四步找剩下1个元素,既是middel[k]的min : 应该是O(K (logN)^2) : 但感觉如果把数组换成一个min-heap存 struct 会得到 O(logK (logN : )^2);
| k**o 发帖数: 3006 | 5 我理解是KlogK * logN?
反正每次取剩下的median of medians,排序, 然后递归…
排序每次是KlogK, 每次淘汰到N/2个数字,所以总共要递归logN次…
然后因为K<=N所以是K(logN)^2?
【在 r*****e 的大作中提到】 : 不太明白 K(logN)^2中的(logN)^2是怎么出来的。。 : 第2-4步,可以找middle数组中的最小和最大,将来丢掉比最小小的,比最大大的。 : : logN)^2);
| r*****e 发帖数: 146 | 6 先赞一个深夜回复。。。
确实应该是median of median.不断丢掉当前一半规模的数据。递归log(N/K)次,因为
最后K个array中,每个array只剩下1个,一共是从总数的N减到K。
问题是,K应该是个不太大,也不太小的数,所以KlogK logN 是不是近似到KlogN?
现在脑子正糊涂。。。
【在 k**o 的大作中提到】 : 我理解是KlogK * logN? : 反正每次取剩下的median of medians,排序, 然后递归… : 排序每次是KlogK, 每次淘汰到N/2个数字,所以总共要递归logN次… : 然后因为K<=N所以是K(logN)^2?
| r*****e 发帖数: 146 | 7 谢谢,可惜不能access acm啊。
btw, I googled this question, found it is also listed as a homework question
. So, i guess 用论文的方法是否有些(我猜的啊,我还没看到论文)杀鸡用牛刀?毕
竟是STOC上的论文。。。
【在 l*****a 的大作中提到】 : who has the access to acm? : these is a paper on this question. : http://apps.topcoder.com/forums/;jsessionid=8B028A73959B4AF354C
| c********t 发帖数: 5706 | 8 为啥要每次排序klogk?
单是找min,就是K
如果第一次排好序,以后删除头,新的值来,binary插入应该的位置,即可。其实就是
min-heap,logK
【在 k**o 的大作中提到】 : 我理解是KlogK * logN? : 反正每次取剩下的median of medians,排序, 然后递归… : 排序每次是KlogK, 每次淘汰到N/2个数字,所以总共要递归logN次… : 然后因为K<=N所以是K(logN)^2?
| s******n 发帖数: 226 | 9 小想法:
1. 初始K个坐标对 [0, Ni-1]
2. 求第一个数组的media-- M1
3,去找剩下有多少比M1小的 (K*lgn)
4,shrink坐标对,退化成找第k大元素
复杂度应该是K*(logN)^2 (upper bound) | l*******b 发帖数: 2586 | 10 嗯,selection rank 的变种吧。k时间找到median of median. selection 就是对每
个数列做binary search ln a1+...+ln ak ~k ln n - k ln k ~ kln n. 一共有n个数
所以一共ln n次selection 于是得到k ln n ln n
【在 r*****e 的大作中提到】 : 先赞一个深夜回复。。。 : 确实应该是median of median.不断丢掉当前一半规模的数据。递归log(N/K)次,因为 : 最后K个array中,每个array只剩下1个,一共是从总数的N减到K。 : 问题是,K应该是个不太大,也不太小的数,所以KlogK logN 是不是近似到KlogN? : 现在脑子正糊涂。。。
|
|