首页 > 代码库 > Median of Two Sorted Arrays

Median of Two Sorted Arrays

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)).

题意:寻找两个有序数组的中位数,要求复杂度为O(log (m+n)).
思路:问题本质其实就是求两个有序数组的第Kth的数,那么我们可以这样考虑,分别求出a,b两个数组中第k/2th的数,这两个数有三种情况

          当a[k/2]<b[k/2]时,那么原kth数肯定不在a[k/2]之前的数内,然后抛弃a[k/2]之前的所有数,再在剩余的数里求k-(k/2)th数,其余两种情况同理,递归二分,所以复杂度降到对数级别


double find_kth(int a[],int m,int b[],int n,int k){
    if(m>n)
      return find_kth(b,n,a,m,k);
    if(m==0)
      return b[k-1];
    if(k==1)
      return min(a[0],b[0]);
    int pa=min(k/2,m),pb=k-pa;
    if(a[pa-1]<b[pb-1])
      return find_kth(a+pa,m-pa,b,n,k-pa);
    else if(a[pa-1]>b[pb-1])
           return find_kth(a,m,b+pb,n-pb,k-pb);
         else
           return a[pa-1];
}


class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int sum=m+n;
        if(sum%2){
            return find_kth(A,m,B,n,sum/2+1);
        }
        else
            return (find_kth(A,m,B,n,sum/2)+find_kth(A,m,B,n,sum/2+1))/2;
    }
};


Median of Two Sorted Arrays