code第一部分数组：两个有序数组的中位数

 

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)).

解决方案1

时间复杂度O(M+N),空间复杂度为O（1）；

方法2

时间复杂度O(log（M+N）),空间复杂度为O（1）

假设 A 和 B 的元素个数都大于 k/2，我们将 A 的第 k/2 个元素（即 A[k/2-1]）和 B 的第 k/2

个元素（即 B[k/2-1]）进行比较，有以下三种情况（为了简化这里先假设 k 为偶数，所得到的结

论对于 k 是奇数也是成立的）：

• A[k/2-1] == B[k/2-1]

• A[k/2-1] > B[k/2-1]

• A[k/2-1] < B[k/2-1]

如果 A[k/2-1] < B[k/2-1]，意味着 A[0] 到 A[k/2-1 的肯定在 A ∪ B 的 top k 元素的范围

内，换句话说， A[k/2-1 不可能大于 A ∪ B 的第 k 大元素。留给读者证明。

因此，我们可以放心的删除 A 数组的这 k/2 个元素。同理，当 A[k/2-1] > B[k/2-1] 时，可

以删除 B 数组的 k/2 个元素。

当 A[k/2-1] == B[k/2-1] 时，说明找到了第 k 大的元素，直接返回 A[k/2-1] 或 B[k/2-1]

即可。

因此，我们可以写一个递归函数。那么函数什么时候应该终止呢？

• 当 A 或 B 是空时，直接返回 B[k-1] 或 A[k-1]；

• 当 k=1 是，返回 min(A[0], B[0])；

• 当 A[k/2-1] == B[k/2-1] 时，返回 A[k/2-1] 或B[k/2-1]；

#include 
     
      using namespace std;double findkth1(int a[],int m,int b[],int n,int k){    if (m==0)    {        return b[k-1];    }    if (n==0)    {        return a[k-1];    }    int i=0;    int j=0;    int count=0;    int target;    while(count
      
        n) return findkth2(b, n, a, m, k);    if (m == 0) return b[k - 1];    if (k == 1) return min(a[0], b[0]);    //divide k into two parts    int pa = min(k / 2, m), pb = k - pa;    if (a[pa - 1] < b[pb - 1])        return findkth2(a + pa, m - pa, b, n, k - pa);    else if (a[pa - 1] > b[pb - 1])        return findkth2(a, m, b + pb, n - pb, k - pb);    else        return a[pa - 1];}double findmedium2(int a[],int m,int b[],int n){    int k=m+n;    if (k%2!=0)    {        return findkth2(a,m,b,n,k/2+1);    }    else        return (findkth2(a,m,b,n,k/2)+findkth2(a,m,b,n,k/2+1))/2;}int main(){    int a[4]={
   1,3,5,7};    int b[4]={
   0,2,4,6};    double ans1=findmedium1(a,4,b,4);    cout<<"ans1 is "<
       
        <
       
      
     

测试通过！