Online Judge Solutions

Thursday, December 25, 2014

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)).
Example
For A = [1,2,3,4,5,6] B = [2,3,4,5], the median is 3.5
For A = [1,2,3] B = [4,5], the median is 4
 
class Solution {
public:
    double findK(vector<int> A, int aStart, int aCount, vector<int> B, int bStart, int bCount, int K)
    {
        if (aCount > bCount) return findK(B, bStart, bCount, A, aStart, aCount, K);
        if (aCount == 0) return B[bStart+K-1];
        if (K == 1) return min(A[aStart], B[bStart]);
        
        int aMid = min(aCount, K/2);
        int bMid = K-aMid;
        
        if (A[aStart+aMid-1] <= B[bStart+bMid-1]) 
            return findK(A, aStart+aMid, aCount-aMid, B, bStart, bCount, K-aMid);
        else         
            return findK(A, aStart, aCount, B, bStart + bMid, bCount-bMid, K-bMid);
    }
    double findMedianSortedArrays(vector<int> A, int m, vector<int> B, int n) {
        if ((m+n)%2) {
            return findK(A, 0, m, B, 0, n, (m+n)/2 + 1);
        }
        
        return (findK(A, 0, m, B, 0, n, (m+n)/2)+findK(A, 0, m, B, 0, n, (m+n)/2+1))/2;
    }
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    double findMedianSortedArrays(vector<int> A, vector<int> B) {
        return findMedianSortedArrays(A, A.size(), B, B.size());
    }
};

 
class Solution {
public:
    double findK(int A[], int aCount, int B[], int bCount, int K)
    {
        if (aCount > bCount) return findK(B, bCount, A, aCount, K);
        if (aCount == 0) return B[K-1];
        if (K == 1) return min(A[0], B[0]);
        
        int aMid = min(aCount, K/2);
        int bMid = K-aMid;
        
        if (A[aMid-1] <= B[bMid-1]) 
            return findK(A+aMid,aCount-aMid, B, bCount, K-aMid);
        else         
            return findK(A, aCount, B+bMid, bCount-bMid, K-bMid);
    }
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if ((m+n)%2) {
            return findK(A, m, B, n, (m+n)/2 + 1);
        }
        
        return (findK(A, m, B, n, (m+n)/2)+findK(A, m, B, n, (m+n)/2+1))/2;
    }
};

No comments:

Post a Comment