g**********y
发帖数: 14569 | 1 刚才看见问面试题，我理解错了，这是错误的理解：
Given P machines, each containing an array of N elements, find the median of
the N*P elements.
好象不是很简单的一道题。
P=2，sorted array时，ihasleetcode上有经典答案。
P是任意数，按类似的方法，写code就不简单，复杂度也不小。
有什么好办法？ |
s*****y
发帖数: 897 | 2 觉得是用
http://en.wikipedia.org/wiki/Selection_algorithm
但是没有code过。
of
【在 g**********y 的大作中提到】
: 刚才看见问面试题，我理解错了，这是错误的理解：
: Given P machines, each containing an array of N elements, find the median of
: the N*P elements.
: 好象不是很简单的一道题。
: P=2，sorted array时，ihasleetcode上有经典答案。
: P是任意数，按类似的方法，写code就不简单，复杂度也不小。
: 有什么好办法？
|
d*******d
发帖数: 2050 | |
g**********y
发帖数: 14569 | 4 如果不能move data around, 就没法用heap.
【在 d*******d 的大作中提到】
: 感觉上下双heap就可以.不知道有没有更好的.
|
d*******d
发帖数: 2050 | |
g**********y
发帖数: 14569 | 6 比较粗糙的想法：
- 给定任何一个数A，我们可以在O(P*N)内确定这个数的位置，办法：
1. 对机器i, 逐个比较，可以知道k[i]个数小于等于A，N-k[i]个比A大
2. 所以A就是第sum(k[..])个数
- 我们目标是找第t = P*N/2个数 (median)
- 用二分法找出机器1里的这个点i, 满足：
a1[i] 是第x个数
a1[i+1] 是第y个数
x < t < y
复杂度 = O(P*N*log(N))
- 那么我们就知道，第t个数(median)的值一定是夹在a1[i]和a1[i+1]之间的。
- 类推下去，找机器2的这个点i'，。。。直到机器P
- 在某个机器上，用以上办法一定可以找到这个点i, 正好是median.
复杂度 = O(P*N*log(N)*P) |
g**********y
发帖数: 14569 | 7 挨个读一遍怎么找出所有的值的median?
【在 d*******d 的大作中提到】
: 不移动data啊,就是挨个读一遍
|
M**u
发帖数: 10158 | 8 还是一样吧
sort N个，然后对N个做归并，每次找出最小的那个扔掉，扔到第NP/2个就行了。。。
of
【在 g**********y 的大作中提到】
: 刚才看见问面试题，我理解错了，这是错误的理解：
: Given P machines, each containing an array of N elements, find the median of
: the N*P elements.
: 好象不是很简单的一道题。
: P=2，sorted array时，ihasleetcode上有经典答案。
: P是任意数，按类似的方法，写code就不简单，复杂度也不小。
: 有什么好办法？
|
g**********y
发帖数: 14569 | 9 这个需要把所有的数都归并到一个机器上，题目要求不能挪数。
【在 M**u 的大作中提到】
: 还是一样吧
: sort N个，然后对N个做归并，每次找出最小的那个扔掉，扔到第NP/2个就行了。。。
:
: of
|
d*******d
发帖数: 2050 | 10 没挪走，make copy都不行。
【在 g**********y 的大作中提到】
: 这个需要把所有的数都归并到一个机器上，题目要求不能挪数。
|
g**********y
发帖数: 14569 | 11 问这种题，一般都针对海量数据，没办法在一台机器上处理。
【在 d*******d 的大作中提到】
: 没挪走，make copy都不行。
|
a**********2
发帖数: 340 | 12
好想不行，因为每次递归重新分组的时候还是需要move data
【在 s*****y 的大作中提到】
: 觉得是用
: http://en.wikipedia.org/wiki/Selection_algorithm
: 但是没有code过。
:
: of
|
d*******d
发帖数: 2050 | 13 我觉得这个对.
归并的时候不用存下来,而是计数就可以.
【在 M**u 的大作中提到】
: 还是一样吧
: sort N个，然后对N个做归并，每次找出最小的那个扔掉，扔到第NP/2个就行了。。。
:
: of
|
