d****e
发帖数: 251 | 1 正解。你是说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.
复杂的就是数组重叠部分，不过应该很快。 |
|
j**l
发帖数: 2911 | 2 如果有序序列的长度为奇数，则median就是正中间的那个数
如果有序序列的长度为偶数，则median是中间的那两个数，有三种处理：
1. 返回median1和median2
2. 返回median1
3. 返回(median1 + median2) / 2.0 |
|
Q******e
发帖数: 85 | 3 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. |
|
n******h
发帖数: 50 | 4 美女，
if (median1 == median2)
不如
return median1; |
|
f******e
发帖数: 164 | 5 你这个解法不对吧。如果m==n是对的，m!=n 不对了。
比方说，按照你的解法，当median1 == median2你怎么办？（不是第一个loop的）。
你用两个不等长的array做例子推演一下就会发现。 |
|
g*******y
发帖数: 1930 | 6 median1 == median2的时候，任务不就已经完成了吗。。。
如果定义偶数个数组的median是两个准median的平均值的话，任务到此为止。即便你定
义偶数个数数组的中位数有两个的情况，最多在加上常数的操作就ok了。 |
|
