f******e
发帖数: 164 | 1 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
这个已经 lineal了？难道还有更快的？ |
y*******g
发帖数: 6599 | 2 电面还是onsite?
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
f******e
发帖数: 164 | 3 电面。
【在 y*******g 的大作中提到】
: 电面还是onsite?
|
I******T
发帖数: 671 | 4 不就是X的median加Y的median吗?
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
D******n
发帖数: 2836 | 5 顯然不是。。。。
【在 I******T 的大作中提到】
: 不就是X的median加Y的median吗?
|
f******e
发帖数: 164 | 6 不对吧。
X = 4,5,6
Y = 1,2,3,7
求的是4
你的X的median加Y的median = 5+2 =7
【在 I******T 的大作中提到】
: 不就是X的median加Y的median吗?
|
D******n
发帖数: 2836 | 7 可以分情況啊，
x=1,2,3,4
y=5,6,7,8
顯然就不用怎麼算
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
r****o
发帖数: 1950 | 8 Union是说X和Y合并后的sorted array吗？
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
Q******e
发帖数: 85 | 9 It can be log(m+n). I can not remember clearly. The basic idea is
suppose array1 = left1[..], median1, right1[...]
suppose array2 = left2[..], median2, right2[...]
we compare meidan1 and median 2,
if meidan1 < median 2
then array1 = right[1], median1 = find_median(array1 ); // array
array2 = left[2], median2 = find_median(array2 );
Repeat until you have two elements left. This is your median.
Maybe some details missing here. |
r****o
发帖数: 1950 | 10 1,2,3,7的median是2还是2.5?
【在 f******e 的大作中提到】
: 不对吧。
: X = 4,5,6
: Y = 1,2,3,7
: 求的是4
: 你的X的median加Y的median = 5+2 =7
|
|
|
n****n
发帖数: 104 | 11 for array N(1..n) and M(1..m), n > m
pick i from M (random, m/2, either way)
search i position in N, say k,
compare i+k and n+m/2, if larger, pick item in the (i+ k)/2 , if less, check
item with order of ((m-i) + (n-k))/2), the new item could be in N or M. if
new item in N, check the position in M, repeat the procedure till you find
it. |
c*****e
发帖数: 210 | 12 可以二分法。 O(logn)时间
先假设median在X中，
比较X[p_x]和Y[size_y/2+size_x/2-p_x], 若>, 则p_x前移， 否则后移。
若X里找不到，
反过来从Y里找 |
y*******g
发帖数: 6599 | 13 嗯, 就是这个意思.
【在 Q******e 的大作中提到】
: It can be log(m+n). I can not remember clearly. The basic idea is
: suppose array1 = left1[..], median1, right1[...]
: suppose array2 = left2[..], median2, right2[...]
: we compare meidan1 and median 2,
: if meidan1 < median 2
: then array1 = right[1], median1 = find_median(array1 ); // array
: array2 = left[2], median2 = find_median(array2 );
: Repeat until you have two elements left. This is your median.
: Maybe some details missing here.
|
g*******y
发帖数: 1930 | 14 log(n+m):
比较X的中位和Y的中位，假设X大，然后可以甩掉X后半和Y前半元素
然后在剩下的m/2 + n/2个元素中用同样的方法
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
I******T
发帖数: 671 | 15 你把题目改成 X Union Y了。
【在 f******e 的大作中提到】
: 不对吧。
: X = 4,5,6
: Y = 1,2,3,7
: 求的是4
: 你的X的median加Y的median = 5+2 =7
|
M*****a
发帖数: 2054 | 16 找出各自的median,然后缩小搜索范围即可
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
g*******y
发帖数: 1930 | 17 呵呵，我回复晚了，原来前面都已经有人给了答案。
random的worst case,应该是O（n)了。比较中位数的话，每次能扔掉几乎正好一半的数。
check
if
【在 n****n 的大作中提到】
: for array N(1..n) and M(1..m), n > m
: pick i from M (random, m/2, either way)
: search i position in N, say k,
: compare i+k and n+m/2, if larger, pick item in the (i+ k)/2 , if less, check
: item with order of ((m-i) + (n-k))/2), the new item could be in N or M. if
: new item in N, check the position in M, repeat the procedure till you find
: it.
|
y*******g
发帖数: 6599 | 18 k largest也不用O(n)方法类似. log
数。
【在 g*******y 的大作中提到】
: 呵呵，我回复晚了，原来前面都已经有人给了答案。
: random的worst case,应该是O（n)了。比较中位数的话，每次能扔掉几乎正好一半的数。
:
: check
: if
|
f******e
发帖数: 164 | 19 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
你用两个不等长的array做例子推演一下就会发现。
【在 Q******e 的大作中提到】
: It can be log(m+n). I can not remember clearly. The basic idea is
: suppose array1 = left1[..], median1, right1[...]
: suppose array2 = left2[..], median2, right2[...]
: we compare meidan1 and median 2,
: if meidan1 < median 2
: then array1 = right[1], median1 = find_median(array1 ); // array
: array2 = left[2], median2 = find_median(array2 );
: Repeat until you have two elements left. This is your median.
: Maybe some details missing here.
|
y*******g
发帖数: 6599 | 20 有一些细节要注意, 如果这么解的话, 要记录下drop了多少small的element
当drop了 n/2的时候停止.
【在 f******e 的大作中提到】
: 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
: 比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
: 你用两个不等长的array做例子推演一下就会发现。
|
|
|
g*******y
发帖数: 1930 | 21 median1 == median2的时候，任务不就已经完成了吗。。。
如果定义偶数个数组的median是两个准median的平均值的话，任务到此为止。即便你定
义偶数个数数组的中位数有两个的情况，最多在加上常数的操作就ok了。
【在 f******e 的大作中提到】
: 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
: 比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
: 你用两个不等长的array做例子推演一下就会发现。
|
r****o
发帖数: 1950 | 22 弱问，请问两个数组X和Y的union是什么意思阿？
是X和Y合并后再sort的数组吗？
【在 g*******y 的大作中提到】
: median1 == median2的时候，任务不就已经完成了吗。。。
: 如果定义偶数个数组的median是两个准median的平均值的话，任务到此为止。即便你定
: 义偶数个数数组的中位数有两个的情况，最多在加上常数的操作就ok了。
|
M*****a
发帖数: 2054 | 23 任务完成的时候就是两个字段长度都为1
【在 g*******y 的大作中提到】
: median1 == median2的时候，任务不就已经完成了吗。。。
: 如果定义偶数个数组的median是两个准median的平均值的话，任务到此为止。即便你定
: 义偶数个数数组的中位数有两个的情况，最多在加上常数的操作就ok了。
|
y*******g
发帖数: 6599 | 24 加起来<=3就可以了吧?
【在 M*****a 的大作中提到】
: 任务完成的时候就是两个字段长度都为1
|
r*****n
发帖数: 120 | 25 2.5
【在 r****o 的大作中提到】
: 1,2,3,7的median是2还是2.5?
|
i**S
发帖数: 105 | 26 我觉得你说得对。
【在 c*****e 的大作中提到】
: 可以二分法。 O(logn)时间
: 先假设median在X中，
: 比较X[p_x]和Y[size_y/2+size_x/2-p_x], 若>, 则p_x前移， 否则后移。
: 若X里找不到，
: 反过来从Y里找
|
s*********l
发帖数: 103 | 27 http://fayaa.com/tiku/view/114/
http://blog.csdn.net/hhygcy/archive/2009/09/23/4584064.aspx
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
m*********y
发帖数: 127 | 28 能不能告诉我 facebook的猎头的email
谢谢了
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
y*******g
发帖数: 6599 | 29 你不是面过么?
【在 m*********y 的大作中提到】
: 能不能告诉我 facebook的猎头的email
: 谢谢了
:
: 不满意。
|
l**********d
发帖数: 19 | 30 第几轮？电面还是onsite？
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
|
|
z********y
发帖数: 109 | 31 log(max(m, n))
【在 g*******y 的大作中提到】
: log(n+m):
: 比较X的中位和Y的中位，假设X大，然后可以甩掉X后半和Y前半元素
: 然后在剩下的m/2 + n/2个元素中用同样的方法
:
: 不满意。
|
l***8
发帖数: 149 | 32 O(log(m+n)) and O(log(max(m,n))) are asymptotically the same thing
【在 z********y 的大作中提到】
: log(max(m, n))
|
c****l
发帖数: 138 | 33 I have a question: since the question asks for the median of X U Y, what if
X and Y have some elements in common? The number of common elemements can be
from 0 to min(m, n), right? Thanks. |
a****n
发帖数: 1887 | 34 在两个数组上用binary search
if arry1mid < array2mid, 去掉前arry1前一半， array2 后一半
else 去掉arry1 后一半，array2 前一半 |
z***e
发帖数: 5393 | 35 search和sort是两个不同的目的，题目只是要你search,你上来就说我要merge sort，
那就已经完全不对，当然不满意。
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
r*******n
发帖数: 3020 | 36 我们不能冲动地把[A[0],A[n/2])和[B[m/2],B[m]]全部扔掉
这个是为什么？ |
S******n
发帖数: 1009 | 37 if m>>n, then, the median which should be in B will be removed after several
cuts
【在 r*******n 的大作中提到】
: 我们不能冲动地把[A[0],A[n/2])和[B[m/2],B[m]]全部扔掉
: 这个是为什么？
|
E*******0
发帖数: 465 | |
S******A
发帖数: 1002 | 39 其实核心是每次两边甩掉的数目要保证相同
我觉得如果两个ARRAY 大小不一样，paddle是最简单的方法
【在 r*******n 的大作中提到】
: 我们不能冲动地把[A[0],A[n/2])和[B[m/2],B[m]]全部扔掉
: 这个是为什么？
|
p******n
发帖数: 156 | 40 这个方法怎么work的?
譬如,给两个array:
1 2 3 4 5 6 7 8 9 10 11
123
????
【在 Q******e 的大作中提到】
: It can be log(m+n). I can not remember clearly. The basic idea is
: suppose array1 = left1[..], median1, right1[...]
: suppose array2 = left2[..], median2, right2[...]
: we compare meidan1 and median 2,
: if meidan1 < median 2
: then array1 = right[1], median1 = find_median(array1 ); // array
: array2 = left[2], median2 = find_median(array2 );
: Repeat until you have two elements left. This is your median.
: Maybe some details missing here.
|
|
|
c**********e
发帖数: 2007 | 41
What is paddle? Detail?
【在 S******A 的大作中提到】
: 其实核心是每次两边甩掉的数目要保证相同
: 我觉得如果两个ARRAY 大小不一样，paddle是最简单的方法
|
n******h
发帖数: 50 | 42 美女，
if (median1 == median2)
不如
return median1;
【在 f******e 的大作中提到】
: 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
: 比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
: 你用两个不等长的array做例子推演一下就会发现。
|
y******0
发帖数: 64 | |
p********7
发帖数: 549 | |
p********7
发帖数: 549 | 45 找到X的median和y的，然后比较之后再找，简单很多
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
a****l
发帖数: 8211 | 46 array中找median就不算时间了?
【在 Q******e 的大作中提到】
: It can be log(m+n). I can not remember clearly. The basic idea is
: suppose array1 = left1[..], median1, right1[...]
: suppose array2 = left2[..], median2, right2[...]
: we compare meidan1 and median 2,
: if meidan1 < median 2
: then array1 = right[1], median1 = find_median(array1 ); // array
: array2 = left[2], median2 = find_median(array2 );
: Repeat until you have two elements left. This is your median.
: Maybe some details missing here.
|
l******t
发帖数: 12659 | 47 求median,不就是求中间数吗?
既然X, Y都是sorted的了,
很容易得到最小值和最大值啊 |
d****e
发帖数: 251 | 48 这解法是错的。
【在 Q******e 的大作中提到】
: It can be log(m+n). I can not remember clearly. The basic idea is
: suppose array1 = left1[..], median1, right1[...]
: suppose array2 = left2[..], median2, right2[...]
: we compare meidan1 and median 2,
: if meidan1 < median 2
: then array1 = right[1], median1 = find_median(array1 ); // array
: array2 = left[2], median2 = find_median(array2 );
: Repeat until you have two elements left. This is your median.
: Maybe some details missing here.
|
d****e
发帖数: 251 | 49 正解。你是说padding? 譬如n < m, 直接将数组一扩充到和数组二一样？
或者每次甩min(n/2, m/2), where n, m are remaining array length.
同时可快速解决一些特例：
if median1 == median2:
return median1
else if median1 < median2:
if arr1[-1] < arr2[0]:
very simple math here.
复杂的就是数组重叠部分，不过应该很快。
【在 S******A 的大作中提到】
: 其实核心是每次两边甩掉的数目要保证相同
: 我觉得如果两个ARRAY 大小不一样，paddle是最简单的方法
|
d****e
发帖数: 251 | 50 因为已经sorted， 不用算时间了。
【在 a****l 的大作中提到】
: array中找median就不算时间了?
|
|
|
i*o
发帖数: 149 | 51 Median is not average.
constant time O(1) for sorted array.
【在 a****l 的大作中提到】
: array中找median就不算时间了?
|
f**********r
发帖数: 2137 | 52 这种问题，复杂度肯定是log的，至于解法再慢慢想 |
x****r
发帖数: 99 | 53 恩，我也觉得padding是个好方法，不然很难搞
如果用一次扔一半那种方法如果碰到
a1 = 10,20,30,40,50
a2 = 45
不知道怎么才可以排除
如果用padding，在a2里面填上2个-1000和2个1000就可以继续做了
不过如果两个数组相差是奇数，怎么填充呢，因为不能两边加上一样的个数
比如
a1 = 1 2 3 4 5 6
a2 = 3
这种情况下median肯定是存在的一个数而不是两个数的平均值，倒是可以用前面一个人
讲过的，现
在a1里面binary search找不到再去a2找，肯定能找到
【在 S******A 的大作中提到】
: 其实核心是每次两边甩掉的数目要保证相同
: 我觉得如果两个ARRAY 大小不一样，paddle是最简单的方法
|
c***p
发帖数: 221 | 54 A detailed solution
http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf
两种办法：
1. suppose an element in one array, use binary search to find the median; if
not find, repeat the same search on the other array
2. remove half elements by comparing median of the two array
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
|
f*****8
发帖数: 5996 | |
y**i
发帖数: 1112 | 56
两个数组相差是奇数一样可以填充
比如你的例子
a1 = 1 2 3 4 5 6
a2 = 3
可以把a2写成-Inf -Inf 3 Inf Inf Inf，（这里用Inf表示无穷大，整数的上限）
那么同样的方法（比较中位数扔掉一半）最后得到两个中位数取小的（因为多加了一个
Inf在右边）
如果把a2写成-Inf -Inf -Inf 3 Inf Inf，那么最后得到两个中位数取大的（因为多加
了一个-Inf在左边）
不过对于第二种方法，对这个例子比较特殊，没有等到最后得到两个中位数的时候已经
遇到了a1的中位数3等于a2的中位数3了，所以直接就返回3了
换另一个例子：a1 = 1 2 3 4 5 6 7 8, a2 = 0, 第一种方法返回4和5中的4，第二种
方法返回3和4中的4。
【在 x****r 的大作中提到】
: 恩，我也觉得padding是个好方法，不然很难搞
: 如果用一次扔一半那种方法如果碰到
: a1 = 10,20,30,40,50
: a2 = 45
: 不知道怎么才可以排除
: 如果用padding，在a2里面填上2个-1000和2个1000就可以继续做了
: 不过如果两个数组相差是奇数，怎么填充呢，因为不能两边加上一样的个数
: 比如
: a1 = 1 2 3 4 5 6
: a2 = 3
|
W***i
发帖数: 9134 | 57 如果 1 2 3 4 5 6 7 8 median是几啊？4和5都算？ |
t******e
发帖数: 1293 | 58 4/5分别是下/上median
【在 W***i 的大作中提到】
: 如果 1 2 3 4 5 6 7 8 median是几啊？4和5都算？
|
