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)).
求两个有序数组的中位数，如果总元素个数是偶数，中位数是中间两个元素的平均值
详细讲解请参考我的另一篇博文：求两个有序数组的中位数或者第k小元素，那篇博文中如果数组总元素个数是偶数，求的是上中位数。
对于那篇博文中的算法2，这一题不能简单的套用，因为如果按照算法2的删除规则，当元素个数是偶数时，有可能把某个中位数删除了，比如对于数组【3,4】，【1,2,5,6】，比较4、5后就会把第一个数组中的3删除，但是3是要参与中位数的计算的。因此对于偶数个数的数组，我们加了一些判断，但是很复杂，代码如下，这里不推荐这种做法
我们可以对那篇博客中算法2稍作修改就可以求下中位数，因此当两个数组总元素时偶数时，求上中位数和下中位数，然后求均值
最优雅的方法是调用那篇博客中算法3求两个有序数组第k小元素的方法 本文地址
1 class Solution { 2 public: 3 double findMedianSortedArrays(int A[], int m, int B[], int n) { 4 int mid_a = m/2, mid_b = n/2; 5 if(m == 0) 6 { 7 if(n % 2 == 0) 8 return (B[mid_b] + B[mid_b-1]) / 2.0; 9 else return B[mid_b]; 10 } 11 else if(n == 0) 12 { 13 if(m % 2 == 0) 14 return (A[mid_a] + A[mid_a-1]) / 2.0; 15 else return A[mid_a]; 16 } 17 18 if((m+n) % 2) 19 return findKthSmallest(A, m, B, n, (m+n+1)/2); 20 else return (findKthSmallest(A, m, B, n, (m+n)/2) + findKthSmallest(A, m, B, n, (m+n)/2+1)) / 2.0; 21 } 22 //找到两个有序数组中第k小的数,k>=1 23 int findKthSmallest(int vec1[], int n1, int vec2[], int n2, int k) 24 { 25 //边界条件处理 26 if(n1 == 0)return vec2[k-1]; 27 else if(n2 == 0)return vec1[k-1]; 28 if(k == 1)return vec1[0] < vec2[0] ? vec1[0] : vec2[0]; 29 30 int idx1 = n1*1.0 / (n1 + n2) * (k - 1); 31 int idx2 = k - idx1 - 2; 32 33 if(vec1[idx1] == vec2[idx2]) 34 return vec1[idx1]; 35 else if(vec1[idx1] < vec2[idx2]) 36 return findKthSmallest(&vec1[idx1+1], n1-idx1-1, vec2, idx2+1, k-idx1-1); 37 else 38 return findKthSmallest(vec1, idx1+1, &vec2[idx2+1], n2-idx2-1, k-idx2-1); 39 } 40 };
本文转自tenos博客园博客，原文链接：http://www.cnblogs.com/TenosDoIt/p/3675220.html，如需转载请自行联系原作者