首页 > 专题系列 > 算法分析 > 求两个有序数组的中位数-算法导论
2014
07-12

求两个有序数组的中位数-算法导论

Question

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))。

有两个排序的数组,长度都为n,求合并后的排序数组的中位数。

题目是《算法导论》上的一道习题,不过已多次出现在面试题当中。注意,此题中两个数组的长度是相等的。当然,长度不等的话也可以做,只是要多些判断条件。参考leetcode题目 Median of Two Sorted Arrays

方法1 直接遍历

直接的解法是遍历两个数组并计数,类似归并排序里面的有序数组的合并,复杂度为O(n)。代码如下:

#include <iostream>
#include <stdio.h>
using namespace std;

double getMedian(int arr1[],int arr2[], int n){
	int i=0,j=0; //分别是 arr1, arr2的当前下标
	int m1=-1,m2=-1; //保存两个中位数. 由于是2n个,肯定有两个中位数
	for(int cnt=0; cnt<=n; cnt++){
		if( i<n && (arr1[i] < arr2[j] || j >= n )){
			m1 = m2;
			m2 = arr1[i++];
		}else{
			m1 = m2;
			m2 = arr2[j++];
		}
	}
	return (m1+m2)/2.0;
}
int main()
{
	int ar1[] = {1, 12, 15, 26, 38};
	int ar2[] = {2, 13, 17, 30, 45};

    int n1 = sizeof(ar1)/sizeof(ar1[0]);
    int n2 = sizeof(ar2)/sizeof(ar2[0]);
    if (n1 == n2)
        printf("Median is %lf", getMedian(ar1, ar2, n1));
    else
        printf("Doesn't work for arrays of unequal size");
    return 0;
}

方法2 分治法

要求的复杂度为O(log (m+n)),很显然需要用分治法求解。

假设数组A的中位数为m1,数组B为m2,例如:

ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}

m1 = 15 ,m2 = 17 。由于m1<m2,则可以确定中位数即为下面两个子数组的中位数 :

[15, 26, 38]  和 [2, 13, 17]

重复这个步骤,可以得到   m1 = 26 m2 = 13. 得到两个子数组:

[15, 26] 和[13, 17]

这时,由于n=2,无法在继续分下去了。可以直接计算得:

 median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
                       = (max(15, 13) + min(26, 17))/2 
                       = (15 + 17)/2
                       = 16

代码如下:

int median(int arr[], int n)
{
    if (n%2 == 0)
        return (arr[n/2] + arr[n/2-1])/2;
    else
        return arr[n/2];
}

int getMedian(int ar1[], int ar2[], int n) {
	int m1;
	int m2;
	if (n <= 0)
		return -1;
	if (n == 1)
		return (ar1[0] + ar2[0]) / 2;

	if (n == 2)
		return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;

	m1 = median(ar1, n);
	m2 = median(ar2, n);
	/* 相等可直接返回 */
	if (m1 == m2)
		return m1;
	if (m1 < m2) {
		if (n % 2 == 0)
			return getMedian(ar1 + n/2-1, ar2, n/2 + 1);
		else
			return getMedian(ar1 + n/2, ar2, n/2+1);
	} else {
		if (n % 2 == 0)
			return getMedian(ar2 + n/2-1, ar1, n/2+1);
		else
			return getMedian(ar2 + n/2, ar1, n/2+1);
	}
}

int main()
{
	int ar1[] = {1, 12, 10, 26, 38};
	int ar2[] = {2, 13, 17, 30, 45};

    int n1 = sizeof(ar1)/sizeof(ar1[0]);
    int n2 = sizeof(ar2)/sizeof(ar2[0]);
    if (n1 == n2)
        printf("Median is %d", getMedian(ar1, ar2, n1));
    else
        printf("Doesn't work for arrays of unequal size");
    return 0;
}

 

时间复杂度为 O(logn)。

参考:http://www.geeksforgeeks.org/median-of-two-sorted-arrays/


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  3. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }