求两个有序数组的median的平凡解法? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求两个有序数组的median的平凡解法?

求两个有序数组的median的平凡解法?# JobHunting - 待字闺中

K*k2011-11-16 08:11

1 楼

要求in place, 只要求O(m + n)的方法，不需要log(m + n)那个。我写的代码还是觉得太长，怎么简化才能在白板上写的下？
double GetMedian(int A[], int m, int B[], int n)
{
bool odd_length = ((m + n) % 2 == 0)? false : true;
int m1, m2;
int pos = (m + n + 1) / 2;
int count = 0;
int i = 0;
int j = 0;
while (i < m && j < n)
{
count++;

if (A[i] <= B[j])
{
if (count == pos)
{
m1 = A[i];
if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = A[i];
return (m1 + m2) / 2.0;
}
i++;
}
else
{
if (count == pos)
{
m1 = B[j];
if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = B[j];
return (m1 + m2) / 2.0;
}
j++;
}
}
while (i < m)
{
count++;
if (count == pos)
{
m1 = A[i];

if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = A[i];
return (m1 + m2) / 2.0;
}
i++;
}
while (j < n)
{
count++;
if (count == pos)
{
m1 = B[j];
if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = B[j];
return (m1 + m2) / 2.0;
}
j++;
}
return 0.0;
}

f*t2011-11-16 08:11

2 楼

int median(int a[], int m, int b[], int n)
{
int target = (m + n) / 2; // Be careful for overflow
int indexA = 0, indexB = 0;
while(--target) {
if(indexA == m-1)
indexB++;
else if(indexB == n-1)
indexA++;
else if(a[indexA] < b[indexB])
indexA++;
else
indexB++;
}
if((m ^ n) & 1)
return min(a[indexA], b[indexB]);
else
return (a[indexA] + b[indexB]) / 2;
}

K*k2011-11-16 08:11

3 楼

没看明白。
而且当总共的元素个数为偶数的时候，median的定义是中间两个数的平均数。
比如
int A[] = {1};
int B[] = {5, 6, 7, 8, 9};
合并后是{1, 5, 6, 7, 8, 9}, median = (6 + 7) / 2 = 6.5

【在 f*******t 的大作中提到】

: int median(int a[], int m, int b[], int n)
: {
: int target = (m + n) / 2; // Be careful for overflow
: int indexA = 0, indexB = 0;
: while(--target) {
: if(indexA == m-1)
: indexB++;
: else if(indexB == n-1)
: indexA++;
: else if(a[indexA] < b[indexB])

K*k2011-11-16 08:11

4 楼

这道题在ihasleetcode的网站上有巧妙的log(m+n)的解法，但对面试来说太难。
有人onsite的时候被问过这题么？

f*t2011-11-16 08:11

5 楼

要返回平均数的话改下最后的return语句就行。
最好的算法是logk的（找第k小的元素），其实不算难，我觉得面试考这题的机会还是挺多的，背好代
码就行。。。

【在 K*****k 的大作中提到】

: 没看明白。
: 而且当总共的元素个数为偶数的时候，median的定义是中间两个数的平均数。
: 比如
: int A[] = {1};
: int B[] = {5, 6, 7, 8, 9};
: 合并后是{1, 5, 6, 7, 8, 9}, median = (6 + 7) / 2 = 6.5

K*k2011-11-16 08:11

6 楼

你原来的代码对test case
A[] = {1};
B[] = {5, 6, 7, 8, 9};
m = 1
n = 5
结果不对，好像return的时候去引用A[1], 越界了。能否检查一下。

是挺多的，背好代

【在 f*******t 的大作中提到】

: 要返回平均数的话改下最后的return语句就行。
: 最好的算法是logk的（找第k小的元素），其实不算难，我觉得面试考这题的机会还是挺多的，背好代
: 码就行。。。

k*n2011-11-16 08:11

7 楼

我被问过，当时就毛了，最后歇比了
算法上根本没啥难的，各种小细节小边界条件，坑死爹阿
以后见到老印就拿这个问，定了

【在 K*****k 的大作中提到】

: 这道题在ihasleetcode的网站上有巧妙的log(m+n)的解法，但对面试来说太难。
: 有人onsite的时候被问过这题么？

f*t2011-11-16 08:11

8 楼

嗯，确实有bug
在原楼编辑了

【在 K*****k 的大作中提到】

: 你原来的代码对test case
: A[] = {1};
: B[] = {5, 6, 7, 8, 9};
: m = 1
: n = 5
: 结果不对，好像return的时候去引用A[1], 越界了。能否检查一下。
:
: 是挺多的，背好代

B*12011-11-16 08:11

9 楼

1337那个帖子下面有个读者给出的也是最优化的，1337也肯定了那个人的code，而且写
得很简单，就是改mit的解法出来的。
1337那个写得太复杂了。

【在 k****n 的大作中提到】

: 我被问过，当时就毛了，最后歇比了
: 算法上根本没啥难的，各种小细节小边界条件，坑死爹阿
: 以后见到老印就拿这个问，定了

K*k2011-11-16 08:11

10 楼

那个log(m + n)的算法现场想到还是很难的，好像MIT某个课程的handout中有解答，但
对偶数个元素，也是求出第一个median, 而不是两个median的平均值。
ihasleetcode的网站有完整巧妙的几种解答方法，可惜我觉得对于面试的白板来说，可
用空间太小了，写不下。

【在 k****n 的大作中提到】

: 我被问过，当时就毛了，最后歇比了
: 算法上根本没啥难的，各种小细节小边界条件，坑死爹阿
: 以后见到老印就拿这个问，定了

H*M2011-11-16 08:11

11 楼

跟merge sort比较象，往前爬，同事记住爬的数目，等总共爬了一半，就是中树的附近
？不过边界条件要整一整

得太长，怎么简化才能在白板上写的下？

【在 K*****k 的大作中提到】

: 要求in place, 只要求O(m + n)的方法，不需要log(m + n)那个。我写的代码还是觉得太长，怎么简化才能在白板上写的下？
: double GetMedian(int A[], int m, int B[], int n)
: {
: bool odd_length = ((m + n) % 2 == 0)? false : true;
: int m1, m2;
: int pos = (m + n + 1) / 2;
: int count = 0;
: int i = 0;
: int j = 0;
: while (i < m && j < n)

f*t2011-11-16 08:11

12 楼

lgk查找递归方法不长的，我顺便发个收藏的代码吧。记不得作者是谁……
int findKthFrom2SortedArraysIterative(int *arr1, int *arr2, int k){
int result;
int mid;
int curPosOfArr1 = 0, curPosOfArr2 = 0;
while(k > 1){
mid = k/2;
if(arr1[curPosOfArr1 + mid - 1] < arr2[curPosOfArr2 + mid - 1]){

curPosOfArr1 = curPosOfArr1 + mid;
}else{
curPosOfArr2 = curPosOfArr2 + mid;
}
k = k - mid;
}
if(arr1[curPosOfArr1] > arr2[curPosOfArr2]){
return arr2[curPosOfArr2];
}else{
return arr1[curPosOfArr1];
}

return result;
}
int findKthFrom2SortedArraysRecursion(int *arr1, int *arr2, int k, int
arr1Index, int arr2Index){
if(k == 1){
if(arr1[arr1Index] <= arr2[arr2Index])
return arr1[arr1Index];
else
return arr2[arr2Index];
}
int curPos = k/2;
if(arr1[arr1Index + curPos - 1] <= arr2[arr2Index + curPos - 1])
findKthFrom2SortedArraysRecursion(arr1, arr2, k - curPos, arr1Index
+ curPos, arr2Index);
else
findKthFrom2SortedArraysRecursion(arr1, arr2, k - curPos, arr1Index,
arr2Index + curPos);
}

b*g2011-11-16 08:11

13 楼

大概的还不错。
A[] = {1};
B[] = {5, 6, 7, 8, 9};
m = 1
n = 5
用楼上的例子，你的算法要越界啊，是针对第一个数组arr1在第二次循环的时候。

【在 f*******t 的大作中提到】

: lgk查找递归方法不长的，我顺便发个收藏的代码吧。记不得作者是谁……
: int findKthFrom2SortedArraysIterative(int *arr1, int *arr2, int k){
: int result;
: int mid;
: int curPosOfArr1 = 0, curPosOfArr2 = 0;
: while(k > 1){
: mid = k/2;
: if(arr1[curPosOfArr1 + mid - 1] < arr2[curPosOfArr2 + mid - 1]){
:
: curPosOfArr1 = curPosOfArr1 + mid;

b*g2011-11-16 08:11

14 楼

这个挺好的，不过
最后(m ^ n) & 1 能不能改成 (m==n)啊，要不然太耍深奥了吧。

【在 f*******t 的大作中提到】

A*u2011-11-16 08:11

15 楼

这玩意太复杂了

得太长，怎么简化才能在白板上写的下？

【在 K*****k 的大作中提到】

f*t2011-11-16 08:11

16 楼

这句是用来判断m+n的奇偶性……

【在 b******g 的大作中提到】

: 这个挺好的，不过
: 最后(m ^ n) & 1 能不能改成 (m==n)啊，要不然太耍深奥了吧。

w*p2011-11-16 08:11

17 楼

请教您指的ihasleetcode是http://www.leetcode.com/ 还是http://www.weiming.info/author/ihasleetcode/ 或是其他？
谢谢。
有包子送的哦！

【在 K*****k 的大作中提到】

: 这道题在ihasleetcode的网站上有巧妙的log(m+n)的解法，但对面试来说太难。
: 有人onsite的时候被问过这题么？

C*U2011-11-16 08:11

18 楼

如果是m+n的话，只要用merge那样做就可以了吧。

得太长，怎么简化才能在白板上写的下？

【在 K*****k 的大作中提到】

x*72011-11-16 08:11

19 楼

到底怎么答好呢？leetcode上面找中位数和找kth解法好像不一样吧。

k*p2011-11-16 08:11

20 楼

http://www.leetcode.com/

【在 w********p 的大作中提到】

: 请教您指的ihasleetcode是http://www.leetcode.com/ 还是http://www.weiming.info/author/ihasleetcode/ 或是其他？
: 谢谢。
: 有包子送的哦！

e*e2011-11-16 08:11

21 楼

用merge的方法写了下。
template
T findKthOf2SortedArray1(T P[], int s, T Q[], int t, int k)
{
// assume: 1 <= k <= (s+t)
int i=0, j=0;
for (int l = 0; l < k; l++){
if (i == s) j++;
else if (j == t) i++;
else {
if (P[i] < Q[j]) i++;
else j++;
}
}
if (i == 0) return Q[j-1];
else if (j == 0) return P[i-1];
else return max(P[i-1], Q[j-1]);
}
template
T medianOfTwoSortedArray3(T P[], int s, T Q[], int t)
{
int k = (s + t)/2;
if ( (s+t)%2 == 1 ) return findKthOf2SortedArray1(P,s,Q,t,k+1);
else {
T res1 = findKthOf2SortedArray1(P,s,Q,t,k);
T res2 = findKthOf2SortedArray1(P,s,Q,t,k+1);
return (res1+res2)/2;
}
}

【在 C***U 的大作中提到】

: 如果是m+n的话，只要用merge那样做就可以了吧。
:
: 得太长，怎么简化才能在白板上写的下？