d**0
发帖数: 124 | 1 请教一个题目： k个unsorted arrays，假设都是n个元素。怎么样快速求出median？
不能把所有的array拼到一起再做quick selection。
我用类似quick selection的方法使用同一个pivot element在k个arrays里quick
select，再求
方法应该是这样，但是复杂度分析不出来。一个naive的bound是o(kn),但是这样就和拼
到一起做quick select一样。最后猜了一个o(nlogk)但是自己也不是很信服。
请大牛指教，谢谢！ | l******e
发帖数: 149 | 2 you don't need to physically 把所有的array拼到一起再做quick selection, but
logically.
O(kn) | f*******n
发帖数: 12623 | 3 可以 O(k*log(n)^2)
Binary search in the first array for the index closest to the median. At
each step, binary search in the other (k-1) arrays for the current value in
the first array. Then add the indexes to see if we are before or after the
median. At the end, we are down to one element and we also know the index in
the other arrays. The answer is in one of these.
The bigger binary search is log(n), at each step, we need to do (k-1) * log(
n), so multiplied together we get O(k*log(n)^2) | d**0
发帖数: 124 | 4 这k个arrays是unsorted的啊 你的做法是认为他sorted吧
in
in
log(
【在 f*******n 的大作中提到】
: 可以 O(k*log(n)^2)
: Binary search in the first array for the index closest to the median. At
: each step, binary search in the other (k-1) arrays for the current value in
: the first array. Then add the indexes to see if we are before or after the
: median. At the end, we are down to one element and we also know the index in
: the other arrays. The answer is in one of these.
: The bigger binary search is log(n), at each step, we need to do (k-1) * log(
: n), so multiplied together we get O(k*log(n)^2)
|
|
