Solution:
When met with time of log(n), it occurs to us that binary search should be a good candidate.
revised binary search, divide both array into two parts. ---> find the kth element
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
int aLen = A.length;
int bLen = B.length;
if((aLen + bLen) % 2 != 0)
return getKthElement(A, 0, aLen-1, B, 0, bLen-1, (aLen+bLen)/2+1);
else
return (getKthElement(A, 0, aLen-1, B, 0, bLen-1, (aLen+bLen)/2) +
getKthElement(A, 0, aLen-1, B, 0, bLen-1, (aLen+bLen)/2+1)) * 0.5;
}
public double getKthElement(int[] A, int aBeg, int aEnd, int[] B, int bBeg, int bEnd, int k){ // k >= 1
if(aBeg > aEnd) return B[bBeg + k-1];
if(bBeg > bEnd) return A[aBeg + k-1];
int aMid = (aEnd + aBeg) / 2;
int bMid = (bEnd + bBeg) / 2;
int len = (aMid - aBeg + 1) + (bMid - bBeg + 1);
if(len > k){ // drop a bigger section
if(A[aMid] < B[bMid]){
return getKthElement(A, aBeg, aEnd, B, bBeg, bMid-1, k);
}
else{
return getKthElement(A, aBeg, aMid-1, B, bBeg, bEnd, k);
}
}
else{ // drop a smaller section
if(A[aMid] < B[bMid]){
return getKthElement(A, aMid+1, aEnd, B, bBeg, bEnd, k-(aMid-aBeg+1));
}
else{
return getKthElement(A, aBeg, aEnd, B, bMid+1, bEnd, k-(bMid-bBeg+1));
}
}
}
}
No comments:
Post a Comment