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