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=0,j=0,k = 0; 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)/2]); if((m+n)%2 == 0) mid = (C[(m+n)/2]+C[(m+n)/2-1]+0.0)/2; delete [] C; return mid; } int main(){ int A[] ={1,3} ; int B[] = {2}; cout<<findMedianSortedArrays(A,2,B,1)<<endl; }
Leetcode Median of Two Sorted Arrays,布布扣,bubuko.com
Leetcode Median of Two Sorted Arrays
原文：http://www.cnblogs.com/xiongqiangcs/p/3621860.html