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)).
------------------------------------------------------------------------------------------
a special case of find kth smallest
reference:
http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/
http://blog.csdn.net/yutianzuijin/article/details/11499917
un-solved:
#1 how to determine k's value: int kA = k * lenA / (lenB + lenA)
#2 why is this inclusive: endA = kA
class Solution {
public:
double findKth (int A[], int startA,int endA, int B[], int startB,int endB, int k) {
int lenA = endA - startA + 1;
int lenB = endB - startB + 1;
if (lenA == 0) {
return B[startB + k];
}
if (lenB == 0) {
return A[startA + k];
}
if (k == 0) {
return min(A[startA],B[startB]);
}
int kA = k * lenA / (lenB + lenA); // ???
int kB = k - kA - 1;
kA += startA;
kB += startB;
if (A[kA] == B[kB]) {
return A[kA];
}
if (A[kA] > B[kB]) {
k = k - (kB - startB + 1);
endA = kA; // inclusive, why?
startB = kB + 1;
}else {
k = k - (kA - startA + 1);
startA = kA + 1;
endB = kB; // inclusive
}
return findKth(A,startA,endA,B,startB,endB,k);
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if ((m + n) % 2 == 1) {
return findKth(A,0,m - 1,B,0,n - 1, (m + n) / 2);
}else {
return (findKth(A,0,m - 1,B,0,n - 1, (m + n) / 2) + findKth(A,0,m - 1,B,0,n - 1, (m + n) / 2 - 1)) / 2.0;
}
}
};
Solution #2, reference:
http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf
如果A[i]是中位数，则A[i]比A里i 个数都大， 比B里（m+n）/2 - i 个数都大
j = (m+n)/2 - i - 1
B[j] < A[i] < B[j + 1]
反之，A在B[j]和B[j + 1]的左侧或者右侧
class Solution {
public:
double findMedian (int A[],int B[],int m,int n,int left,int right) {
if (left > right) {
return findMedian(B,A,n,m,max(0,(m+n)/2 - m),min(n,(m+n)/2));
}
int i = (left + right) / 2;
int j = (m + n) / 2 - i - 1;
if (j >= 0 && A[i] < B[j]) {
return findMedian(A,B,m,n,i + 1, right);
}
if (j < n - 1 && A[i] > B[j + 1]) {
return findMedian(A,B,m,n,left,i - 1);
}
if ((m + n) % 2 == 1) {
return A[i];
}
if (i > 0) {
return (A[i] + max(B[j],A[i - 1])) / 2.0;
}
return (A[i] + B[j]) / 2.0;
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if (m > n) {
return findMedian(A,B,m,n,max(0,(m+n)/2 - n),min(m,(m+n)/2));
}
return findMedian(B,A,n,m,max(0,(m+n)/2 - m),min(n,(m+n)/2));
}
};
Another one, takes half of k at each call, key us (k + 1) / 2
#1 当A里的元素不足 k / 2 个时，可以砍掉B的前 k / 2
#2 当 A[k/2] < B[k/2], 可以砍掉A的前 k / 2
以上都可以用反证法证明
k为0-based
- return B[BStart + k]意思为返回第 k + 1（1-based）小的elem
- AK = (k + 1) / 2, 为个数，所以 k 需要 + 1
- AStart + AK - 1, 同样道理，AK是个数（1-based），需要转换为 0-based
- return findKth(,....AStart + AK), AK是要被砍掉的个数，所以不用 - 1
base condition以下，k和AK，BK不可能为0，所以需要 - 1，不然AStart永远取不到
http://www.ninechapter.com/solutions/median-of-two-sorted-arrays/
class Solution {
public:
double findKth(int A[],int m, int AStart, int B[], int n, int BStart, int k) {
if (AStart == m) return B[BStart + k];
if (BStart == n) return A[AStart + k];
if (k == 0) return min(A[AStart],B[BStart]);
int AKey = INT_MAX;
int BKey = INT_MAX;
int AK = (k + 1) / 2;
int BK = (k + 1) / 2;
if (AStart + AK - 1 < m) {
AKey = A[AStart + AK - 1];
}
if (BStart + BK - 1 < n) {
BKey = B[BStart + BK - 1];
}
if (AKey < BKey) {
return findKth(A,m,AStart + AK,B,n,BStart,k - AK);
}else {
return findKth(A,m,AStart,B,n,BStart + BK,k - BK);
}
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int k = n + m;
if (k % 2 == 0) {
return (findKth(A,m, 0, B,n, 0, k / 2 - 1) + findKth(A,m,0, B, n, 0, k / 2)) / 2.0 ;
} else {
return findKth(A,m,0, B, n, 0, k / 2);
}
}
};
