冲上云霄2的主题曲被人骂，感觉我老了。# TVChinese - 中文电视
f*e
1 楼
给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
这个已经 lineal了？难道还有更快的？
如何找到X
这个已经 lineal了？难道还有更快的？
s*n
2 楼
一骗子公司，中国人开的，骗了不知道多少中国人了。去年在他那里做contractor,现
在不给tax documents，怎么报税呢？
在不给tax documents，怎么报税呢？
s*d
3 楼
林子祥唱 的我觉得很好啊。
也不错。本来就不是偶像剧。
结果被HK n多人投诉。
居然还有人这样。
80-90年代这批人的唱功比现在年轻的牛多了。
小P孩懂什么！！！
也不错。本来就不是偶像剧。
结果被HK n多人投诉。
居然还有人这样。
80-90年代这批人的唱功比现在年轻的牛多了。
小P孩懂什么！！！
y*g
4 楼
电面还是onsite?
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
f*e
5 楼
tell IRS ??
e*G
6 楼
是你老了，EASON的比较现代
f*e
7 楼
电面。
【在 y*******g 的大作中提到】
: 电面还是onsite?
【在 y*******g 的大作中提到】
: 电面还是onsite?
s*n
8 楼
up。难道没有人碰到过这种骗人的consulting公司？还是只有我碰到了这种骗人的华人
公司？
【在 s******n 的大作中提到】
: 一骗子公司，中国人开的，骗了不知道多少中国人了。去年在他那里做contractor,现
: 在不给tax documents，怎么报税呢？
公司？
【在 s******n 的大作中提到】
: 一骗子公司，中国人开的，骗了不知道多少中国人了。去年在他那里做contractor,现
: 在不给tax documents，怎么报税呢？
b*r
9 楼
我也老了
【在 s*********d 的大作中提到】
: 林子祥唱 的我觉得很好啊。
: 也不错。本来就不是偶像剧。
: 结果被HK n多人投诉。
: 居然还有人这样。
: 80-90年代这批人的唱功比现在年轻的牛多了。
: 小P孩懂什么！！！
【在 s*********d 的大作中提到】
: 林子祥唱 的我觉得很好啊。
: 也不错。本来就不是偶像剧。
: 结果被HK n多人投诉。
: 居然还有人这样。
: 80-90年代这批人的唱功比现在年轻的牛多了。
: 小P孩懂什么！！！
I*T
10 楼
不就是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了？难道还有更快的？
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
p*t
11 楼
http://www.irs.gov/uac/Here-is-What-to-do-If-You-Are-Missing-a-
【在 s******n 的大作中提到】
: 一骗子公司，中国人开的，骗了不知道多少中国人了。去年在他那里做contractor,现
: 在不给tax documents，怎么报税呢？
【在 s******n 的大作中提到】
: 一骗子公司，中国人开的，骗了不知道多少中国人了。去年在他那里做contractor,现
: 在不给tax documents，怎么报税呢？
m*6
12 楼
这不是唱功的问题，曲风严重跑偏。听岁月如歌想飞，听2这个想跪
D*n
13 楼
顯然不是。。。。
【在 I******T 的大作中提到】
: 不就是X的median加Y的median吗?
【在 I******T 的大作中提到】
: 不就是X的median加Y的median吗?
s*n
14 楼
谢谢~这种大骗子公司，真是要小心上当。怎么样才能给这种骗子公司一些惩罚呢？
【在 p*****t 的大作中提到】
: http://www.irs.gov/uac/Here-is-What-to-do-If-You-Are-Missing-a-
【在 p*****t 的大作中提到】
: http://www.irs.gov/uac/Here-is-What-to-do-If-You-Are-Missing-a-
f*e
15 楼
不对吧。
X = 4,5,6
Y = 1,2,3,7
求的是4
你的X的median加Y的median = 5+2 =7
【在 I******T 的大作中提到】
: 不就是X的median加Y的median吗?
X = 4,5,6
Y = 1,2,3,7
求的是4
你的X的median加Y的median = 5+2 =7
【在 I******T 的大作中提到】
: 不就是X的median加Y的median吗?
t*h
16 楼
你就不能公布他们的资料？
D*n
17 楼
可以分情況啊，
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了？难道还有更快的？
x=1,2,3,4
y=5,6,7,8
顯然就不用怎麼算
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
c*2
18 楼
so they withheld your taxes, but they keep in their pocket and not paying to
IRS? Is there a client company you work for? client will have
contractor's tax info.
Or if cleint/contractor/you all cash payments under the table, of course
there will be no tax info generated.
IRS? Is there a client company you work for? client will have
contractor's tax info.
Or if cleint/contractor/you all cash payments under the table, of course
there will be no tax info generated.
r*o
19 楼
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了？难道还有更快的？
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
c*2
20 楼
so they withheld your taxes, but they keep in their pocket and not paying to
IRS? Is there a client company you work for? client will have
contractor's tax info.
Or if cleint/contractor/you all cash payments under the table, of course
there will be no tax info generated.
IRS? Is there a client company you work for? client will have
contractor's tax info.
Or if cleint/contractor/you all cash payments under the table, of course
there will be no tax info generated.
Q*e
21 楼
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.
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.
s*n
22 楼
谢谢您的回复~这个公司是个很不正规的骗子公司。他没有payrol，没有任何扣税信息
。不是cash payments,他每个月就固定往我账上打2000美元。有client，但是client
pay都是corp to corp. 真是被这个骗子骗得好惨。。。
to
【在 c**2 的大作中提到】
: so they withheld your taxes, but they keep in their pocket and not paying to
: IRS? Is there a client company you work for? client will have
: contractor's tax info.
: Or if cleint/contractor/you all cash payments under the table, of course
: there will be no tax info generated.
。不是cash payments,他每个月就固定往我账上打2000美元。有client，但是client
pay都是corp to corp. 真是被这个骗子骗得好惨。。。
to
【在 c**2 的大作中提到】
: so they withheld your taxes, but they keep in their pocket and not paying to
: IRS? Is there a client company you work for? client will have
: contractor's tax info.
: Or if cleint/contractor/you all cash payments under the table, of course
: there will be no tax info generated.
r*o
23 楼
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
【在 f******e 的大作中提到】
: 不对吧。
: X = 4,5,6
: Y = 1,2,3,7
: 求的是4
: 你的X的median加Y的median = 5+2 =7
r*k
24 楼
这就相当于现金交易了，如果身份没问题的话也无所谓的。
【在 s******n 的大作中提到】
: 谢谢您的回复~这个公司是个很不正规的骗子公司。他没有payrol，没有任何扣税信息
: 。不是cash payments,他每个月就固定往我账上打2000美元。有client，但是client
: pay都是corp to corp. 真是被这个骗子骗得好惨。。。
:
: to
【在 s******n 的大作中提到】
: 谢谢您的回复~这个公司是个很不正规的骗子公司。他没有payrol，没有任何扣税信息
: 。不是cash payments,他每个月就固定往我账上打2000美元。有client，但是client
: pay都是corp to corp. 真是被这个骗子骗得好惨。。。
:
: to
n*n
25 楼
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.
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
26 楼
可以二分法。 O(logn)时间
先假设median在X中，
比较X[p_x]和Y[size_y/2+size_x/2-p_x], 若>, 则p_x前移， 否则后移。
若X里找不到，
反过来从Y里找
先假设median在X中，
比较X[p_x]和Y[size_y/2+size_x/2-p_x], 若>, 则p_x前移， 否则后移。
若X里找不到，
反过来从Y里找
y*g
27 楼
嗯, 就是这个意思.
【在 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.
【在 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
28 楼
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了？难道还有更快的？
比较X的中位和Y的中位，假设X大，然后可以甩掉X后半和Y前半元素
然后在剩下的m/2 + n/2个元素中用同样的方法
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
I*T
29 楼
你把题目改成 X Union Y了。
【在 f******e 的大作中提到】
: 不对吧。
: X = 4,5,6
: Y = 1,2,3,7
: 求的是4
: 你的X的median加Y的median = 5+2 =7
【在 f******e 的大作中提到】
: 不对吧。
: X = 4,5,6
: Y = 1,2,3,7
: 求的是4
: 你的X的median加Y的median = 5+2 =7
M*a
30 楼
找出各自的median,然后缩小搜索范围即可
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
g*y
31 楼
呵呵，我回复晚了，原来前面都已经有人给了答案。
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.
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
32 楼
k largest也不用O(n)方法类似. log
数。
【在 g*******y 的大作中提到】
: 呵呵，我回复晚了，原来前面都已经有人给了答案。
: random的worst case,应该是O（n)了。比较中位数的话，每次能扔掉几乎正好一半的数。
:
: check
: if
数。
【在 g*******y 的大作中提到】
: 呵呵，我回复晚了，原来前面都已经有人给了答案。
: random的worst case,应该是O（n)了。比较中位数的话，每次能扔掉几乎正好一半的数。
:
: check
: if
f*e
33 楼
你这个解法不对吧。如果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.
比方说，按照你的解法，当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
34 楼
有一些细节要注意, 如果这么解的话, 要记录下drop了多少small的element
当drop了 n/2的时候停止.
【在 f******e 的大作中提到】
: 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
: 比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
: 你用两个不等长的array做例子推演一下就会发现。
当drop了 n/2的时候停止.
【在 f******e 的大作中提到】
: 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
: 比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
: 你用两个不等长的array做例子推演一下就会发现。
g*y
35 楼
median1 == median2的时候，任务不就已经完成了吗。。。
如果定义偶数个数组的median是两个准median的平均值的话，任务到此为止。即便你定
义偶数个数数组的中位数有两个的情况，最多在加上常数的操作就ok了。
【在 f******e 的大作中提到】
: 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
: 比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
: 你用两个不等长的array做例子推演一下就会发现。
如果定义偶数个数组的median是两个准median的平均值的话，任务到此为止。即便你定
义偶数个数数组的中位数有两个的情况，最多在加上常数的操作就ok了。
【在 f******e 的大作中提到】
: 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
: 比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
: 你用两个不等长的array做例子推演一下就会发现。
r*o
36 楼
弱问，请问两个数组X和Y的union是什么意思阿？
是X和Y合并后再sort的数组吗？
【在 g*******y 的大作中提到】
: median1 == median2的时候，任务不就已经完成了吗。。。
: 如果定义偶数个数组的median是两个准median的平均值的话，任务到此为止。即便你定
: 义偶数个数数组的中位数有两个的情况，最多在加上常数的操作就ok了。
是X和Y合并后再sort的数组吗？
【在 g*******y 的大作中提到】
: median1 == median2的时候，任务不就已经完成了吗。。。
: 如果定义偶数个数组的median是两个准median的平均值的话，任务到此为止。即便你定
: 义偶数个数数组的中位数有两个的情况，最多在加上常数的操作就ok了。
M*a
37 楼
任务完成的时候就是两个字段长度都为1
【在 g*******y 的大作中提到】
: median1 == median2的时候，任务不就已经完成了吗。。。
: 如果定义偶数个数组的median是两个准median的平均值的话，任务到此为止。即便你定
: 义偶数个数数组的中位数有两个的情况，最多在加上常数的操作就ok了。
【在 g*******y 的大作中提到】
: median1 == median2的时候，任务不就已经完成了吗。。。
: 如果定义偶数个数组的median是两个准median的平均值的话，任务到此为止。即便你定
: 义偶数个数数组的中位数有两个的情况，最多在加上常数的操作就ok了。
y*g
38 楼
加起来<=3就可以了吧?
【在 M*****a 的大作中提到】
: 任务完成的时候就是两个字段长度都为1
【在 M*****a 的大作中提到】
: 任务完成的时候就是两个字段长度都为1
r*n
39 楼
2.5
【在 r****o 的大作中提到】
: 1,2,3,7的median是2还是2.5?
【在 r****o 的大作中提到】
: 1,2,3,7的median是2还是2.5?
i*S
40 楼
我觉得你说得对。
【在 c*****e 的大作中提到】
: 可以二分法。 O(logn)时间
: 先假设median在X中，
: 比较X[p_x]和Y[size_y/2+size_x/2-p_x], 若>, 则p_x前移， 否则后移。
: 若X里找不到，
: 反过来从Y里找
【在 c*****e 的大作中提到】
: 可以二分法。 O(logn)时间
: 先假设median在X中，
: 比较X[p_x]和Y[size_y/2+size_x/2-p_x], 若>, 则p_x前移， 否则后移。
: 若X里找不到，
: 反过来从Y里找
s*l
41 楼
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了？难道还有更快的？
http://blog.csdn.net/hhygcy/archive/2009/09/23/4584064.aspx
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
m*y
42 楼
能不能告诉我 facebook的猎头的email
谢谢了
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
谢谢了
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
y*g
43 楼
你不是面过么?
【在 m*********y 的大作中提到】
: 能不能告诉我 facebook的猎头的email
: 谢谢了
:
: 不满意。
【在 m*********y 的大作中提到】
: 能不能告诉我 facebook的猎头的email
: 谢谢了
:
: 不满意。
l*d
44 楼
第几轮？电面还是onsite？
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
z*y
45 楼
log(max(m, n))
【在 g*******y 的大作中提到】
: log(n+m):
: 比较X的中位和Y的中位，假设X大，然后可以甩掉X后半和Y前半元素
: 然后在剩下的m/2 + n/2个元素中用同样的方法
:
: 不满意。
【在 g*******y 的大作中提到】
: log(n+m):
: 比较X的中位和Y的中位，假设X大，然后可以甩掉X后半和Y前半元素
: 然后在剩下的m/2 + n/2个元素中用同样的方法
:
: 不满意。
l*8
46 楼
O(log(m+n)) and O(log(max(m,n))) are asymptotically the same thing
【在 z********y 的大作中提到】
: log(max(m, n))
【在 z********y 的大作中提到】
: log(max(m, n))
c*l
47 楼
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.
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
48 楼
在两个数组上用binary search
if arry1mid < array2mid, 去掉前arry1前一半， array2 后一半
else 去掉arry1 后一半，array2 前一半
if arry1mid < array2mid, 去掉前arry1前一半， array2 后一半
else 去掉arry1 后一半，array2 前一半
z*e
49 楼
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了？难道还有更快的？
那就已经完全不对，当然不满意。
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
r*n
50 楼
我们不能冲动地把[A[0],A[n/2])和[B[m/2],B[m]]全部扔掉
这个是为什么？
这个是为什么？
S*n
51 楼
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]]全部扔掉
: 这个是为什么？
cuts
【在 r*******n 的大作中提到】
: 我们不能冲动地把[A[0],A[n/2])和[B[m/2],B[m]]全部扔掉
: 这个是为什么？
E*0
52 楼
log(m+n)
S*A
53 楼
其实核心是每次两边甩掉的数目要保证相同
我觉得如果两个ARRAY 大小不一样，paddle是最简单的方法
【在 r*******n 的大作中提到】
: 我们不能冲动地把[A[0],A[n/2])和[B[m/2],B[m]]全部扔掉
: 这个是为什么？
我觉得如果两个ARRAY 大小不一样，paddle是最简单的方法
【在 r*******n 的大作中提到】
: 我们不能冲动地把[A[0],A[n/2])和[B[m/2],B[m]]全部扔掉
: 这个是为什么？
p*n
54 楼
这个方法怎么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.
譬如,给两个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
55 楼
What is paddle? Detail?
【在 S******A 的大作中提到】
: 其实核心是每次两边甩掉的数目要保证相同
: 我觉得如果两个ARRAY 大小不一样，paddle是最简单的方法
n*h
56 楼
美女，
if (median1 == median2)
不如
return median1;
【在 f******e 的大作中提到】
: 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
: 比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
: 你用两个不等长的array做例子推演一下就会发现。
if (median1 == median2)
不如
return median1;
【在 f******e 的大作中提到】
: 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
: 比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
: 你用两个不等长的array做例子推演一下就会发现。
y*0
57 楼
ls都是CS的？
p*7
59 楼
找到X的median和y的，然后比较之后再找，简单很多
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不满意。
: 这个已经 lineal了？难道还有更快的？
不满意。
【在 f******e 的大作中提到】
: 给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
: 如何找到X
: 这个已经 lineal了？难道还有更快的？
a*l
60 楼
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.
【在 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
61 楼
求median,不就是求中间数吗?
既然X, Y都是sorted的了,
很容易得到最小值和最大值啊
既然X, Y都是sorted的了,
很容易得到最小值和最大值啊
d*e
62 楼
这解法是错的。
【在 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.
【在 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
63 楼
正解。你是说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是最简单的方法
或者每次甩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
64 楼
因为已经sorted， 不用算时间了。
【在 a****l 的大作中提到】
: array中找median就不算时间了?
【在 a****l 的大作中提到】
: array中找median就不算时间了?
i*o
65 楼
Median is not average.
constant time O(1) for sorted array.
【在 a****l 的大作中提到】
: array中找median就不算时间了?
constant time O(1) for sorted array.
【在 a****l 的大作中提到】
: array中找median就不算时间了?
f*r
66 楼
这种问题，复杂度肯定是log的，至于解法再慢慢想
x*r
67 楼
恩，我也觉得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是最简单的方法
如果用一次扔一半那种方法如果碰到
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
68 楼
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了？难道还有更快的？
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
: 这个已经 lineal了？难道还有更快的？
f*8
69 楼
.哈哈. 面试"官"
y*i
70 楼
两个数组相差是奇数一样可以填充
比如你的例子
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
71 楼
如果 1 2 3 4 5 6 7 8 median是几啊？4和5都算？
t*e
72 楼
4/5分别是下/上median
【在 W***i 的大作中提到】
: 如果 1 2 3 4 5 6 7 8 median是几啊？4和5都算？
【在 W***i 的大作中提到】
: 如果 1 2 3 4 5 6 7 8 median是几啊？4和5都算？
相关阅读