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)).
将两个有序数组合并，注意题目求得是the median of the two sorted array，
当m+n是奇数时返回的是合并后的中间数即C[(m+n)/2]
当m+n是偶数时返回的是合并后的中间两个数的平均数即(C[(m+n)/2]+C[(m+n)/2-1]+0.0)/2
注意题目求的是double，空间复杂度是O(m+n)
#include <iostream>
#include <vector>
#include <algorithm> using namespace std; double findMedianSortedArrays(int A[], int m, int B[],int n){
int *C = new int[m+n],i=,j=,k = ;
while(i < m && j < n ){
if(A[i] > B[j]) C[k++]=B[j++];
else if(A[i] < B[j]) C[k++] = A[i++];
else { C[k++]=A[i++];C[k++] = B[j++];}
}
if(i < m ){
for(int idx = i ; idx < m ; idx++) C[k++] = A[idx];
}
if( j< n){
for(int idx = j; idx < n; idx++) C[k++] = B[idx];
}
double mid = double(C[(m+n)/]);
if((m+n)% == ) mid = (C[(m+n)/]+C[(m+n)/-]+0.0)/;
delete [] C;
return mid;
} int main(){
int A[] ={,} ;
int B[] = {};
cout<<findMedianSortedArrays(A,,B,)<<endl;
}
利用二分查找，时间复杂度O(log(m+n))
#include <iostream>
#include <algorithm> using namespace std; double findKth(int A[], int m, int B[], int n , int k){
if(m > n){
return findKth(B,n,A,m,k);
}else{
if( m == ) return B[k-];
if( k == ) return min(A[],B[]);
int first = min(k/,m),second = k - first;
if( A[first- ] < B[second-])
return findKth(A+first,m-first,B,n,k-first);
else if(A[first-] > B[second-])
return findKth(A,m,B+second,n-second,k-second);
else return A[first-];
}
} double findMedianSortedArrays(int A[], int m, int B[], int n){
int total = m + n;
if(total & 0x1)
return findKth(A,m,B,n,(total>>)+);
else
return (findKth(A,m,B,n,(total>>)) + findKth(A,m,B,n,(total>>)+))/;
} int main(){
int A[] ={,,} ;
int B[] = {,,};
cout<<findMedianSortedArrays(A,,B,)<<endl;
}