Thursday, June 13, 2013

Leetcode: Median of Two Sorted Arrays in C++



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)).
Either Drop the right side of Bigger one or left side of the small one. 
Solution:
int findMid(int A[], int m,  int B[], int n, int k)
{
        if(m<=0) return B[k-1];
        if(n<=0) return A[k-1];
        if(k<=1)
        return min(A[0], B[0]);
        if(A[m/2]>B[n/2])
        {
            if(m/2+n/2+1<k)
                 return findMid(A, m, B+n/2+1, n - n/2-1, k-n/2-1 );
            else
                return findMid(A, m/2, B, n, k);
        }
        else
        {
            if(m/2+n/2+1<k)
                return findMid(A+m/2+1, m- m/2-1, B, n, k-m/2-1 );
            else
                return findMid(A, m, B, n/2, k);
        }
    }
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if((m+n)%2==0)
        return (findMid(A,m,B,n,(m+n)/2)+findMid(A,m,B,n,(m+n)/2+1))/2.0;
        else
        return findMid(A,m,B,n,(m+n)/2+1);
    }

No comments:

Post a Comment