—— Median of Two Sorted Arrays

4、 Median of Two Sorted Arrays

两个排序数组的中位数

两个排序的数组A和B分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))。

样例

给出数组A = [1,2,3,4,5,6] B = [2,3,4,5]，中位数3.5

给出数组A = [1,2,3] B = [4,5]，中位数 3

挑战 

时间复杂度为O(log n)

具体思路：

求第k个元素，取A[k / 2] B[k / 2] 比较，如果 A[k / 2] > B[k / 2] 那么，所求的元素必然不在B的前k / 2个元素中，

反之，必然不在A的前k / 2个元素中，于是我们可以将A或B数列的前k / 2元素删去，然后使用递归，直到找到k为止。

代码：

class Solution {
public:
    double findkth(vector<int>& A,vector<int>& B,int A_start,int B_start,int median)
    {
        //边界情况，当一边为空时，直接从另一边取元素
        if(A_start>=A.size())
            return B[B_start+median-1];
        if(B_start>=B.size())
            return A[A_start+median-1];
        //当k为1时，直接取最小值
        if(median==1)return min(A[A_start],B[B_start]);
        //A，B都向前走中位数的一半，相互比较，小的一方说明必然不包含所求的元素
        int A_key=A_start+median/2-1>=A.size()?INT_MAX:A[A_start+median/2-1];
        int B_key=B_start+median/2-1>=B.size()?INT_MAX:B[B_start+median/2-1];
        if(A_key<B_key)//比较，小的一方向前移动，median也减去相应的数量
            return findkth(A,B,A_start+median/2,B_start,median-median/2);
        else
            return findkth(A,B,A_start,B_start+median/2,median-median/2);
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int sum=nums1.size()+nums2.size();
        double reulst;
        if(sum&1)//sum是否为2的倍数，是有两个中位数
            return reulst=findkth(nums1,nums2,0,0,sum/2+1);
        else
            return reulst=(findkth(nums1,nums2,0,0,sum/2)+findkth(nums1,nums2,0,0,sum/2+1))/2;
    }
};