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?
: 现在脑子正糊涂。。。
|
|
