Median of Two Sorted Arrays

  1. 云栖社区>
  2. 博客>
  3. 正文

Median of Two Sorted Arrays

指尖的舞曲 2014-11-30 18:32:00 浏览747
展开阅读全文

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

 题解:

首先我们先明确什么是median,即中位数。 

引用Wikipedia对中位数的定义:

计算有限个数的数据的中位数的方法是:把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数,则中间那个数据就是这群数据的中位数;如果数据的个数是偶数,则中间那2个数据的算术平均值就是这群数据的中位数。

因此,在计算中位数Median时候,需要根据奇偶分类讨论。

解决此题的方法可以依照:寻找一个unioned sorted array中的第k大(从1开始数)的数。因而等价于寻找并判断两个sorted array中第k/2(从1开始数)大的数。

特殊化到求median,那么对于奇数来说,就是求第(m+n)/2+1(从1开始数)大的数。

而对于偶数来说,就是求第(m+n)/2大(从1开始数)和第(m+n)/2+1大(从1开始数)的数的算术平均值。

 

那么如何判断两个有序数组A,B中第k大的数呢?

我们需要判断A[k/2-1]和B[k/2-1]的大小。

如果A[k/2-1]==B[k/2-1],那么这个数就是两个数组中第k大的数。

如果A[k/2-1]<B[k/2-1], 那么说明A[0]到A[k/2-1]都不可能是第k大的数,所以需要舍弃这一半,继续从A[k/2]到A[A.length-1]继续找。当然,因为这里舍弃了A[0]到A[k/2-1]这k/2个数,那么第k大也就变成了,第k-k/2个大的数了。

如果 A[k/2-1]>B[k/2-1],就做之前对称的操作就好。

 这样整个问题就迎刃而解了。

 

当然,边界条件页不能少,需要判断是否有一个数组长度为0,以及k==1时候的情况。

 

因为除法是向下取整,并且页为了方便起见,对每个数组的分半操作采取:

int partA = Math.min(k/2,m);
int partB = k - partA; 

 为了能保证上面的分半操作正确,需要保证A数组的长度小于B数组的长度。

 

同时,在返回结果时候,注意精度问题,返回double型的就好。

 

C++实现代码:

#include<iostream>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total=m+n;
        if((m+n)%2)
            return findMedian(A,0,m-1,B,0,n-1,total/2+1);
        else
        {
            int pre=findMedian(A,0,m-1,B,0,n-1,total/2);
            int last=findMedian(A,0,m-1,B,0,n-1,total/2+1);
            return (pre+last)/2;
        }
    }
    double findMedian(int A[],int astart,int aend,int B[],int bstart,int bend,int k)
    {
        int m=aend-astart+1;
        int n=bend-bstart+1;
        if(m>n)
            return findMedian(B,bstart,bend,A,astart,aend,k);
        if(m==0)
            return B[k-1];
        if(k==1)
            return min(A[astart],B[bstart]);
        int partA=min(m,k/2);
        int partB=k-partA;
        if(A[astart+partA-1]<B[bstart+partB-1])
            return findMedian(A,astart+partA,aend,B,bstart,bend,k-partA);
        else if(A[astart+partA-1]>B[bstart+partB-1])
            return findMedian(A,astart,aend,B,bstart+partB,bend,k-partB);
        else
            return A[astart+partA-1];
    }
};

int main()
{
    Solution s;
    int A[5]= {1,2,3,4,5};
    int B[10]= {6,7,8,9};
    cout<<s.findMedianSortedArrays(A,4,B,4)<<endl;
}

使用O(m+n)的复杂度的算法:

#include<iostream>
using namespace std;

class Solution
{
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n)
    {
        int i=0, j=0, median = m+n;
        double prev=0, last=0;

        if(median<2)
        {
            if (m == 0 && n == 0) return 0;
            if (m==1)
                return A[0];
            else
                return B[0];
        }

        while ( (i+j) <= (median/2) )
        {
            prev = last;
            if (i >= m) //如果A中的元素已经用完,直接取B数组
            {
                last=B[j];
                j++;
            }
            else if (j>=n) //同上
            {
                last = A[i];
                i++;
            }
            else if (A[i]<B[j]) //取A[i] 和 B[j] 中较小的
            {
                last = A[i];
                i++;
            }
            else
            {
                last=B[j];
                j++;
            }
        }

        if ((median & 1) == 0) //偶数个
            return (prev + last) / 2.0;
        else //奇数个
            return last;
    }
};

int main()
{
    Solution s;
    int A[5]= {1,2,3,4,5};
    int B[10]= {6,7,8,9};
    cout<<s.findMedianSortedArrays(A,5,B,4)<<endl;
}

 

网友评论

登录后评论
0/500
评论
指尖的舞曲
+ 关注