給定兩個(gè)大小分別為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。請(qǐng)你找出并返回這兩個(gè)正序數(shù)組的 中位數(shù) 。

算法的時(shí)間復(fù)雜度應(yīng)該為 O(log (m+n)) 。

第一種 暴力解法 合并+排序
時(shí)間復(fù)雜度O（m+n）

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        for(vector<int>::iterator it=nums2.begin();it!=nums2.end();it++)
        {
            nums1.push_back(*it);
        }
        sort(nums1.begin(),nums1.end());
        double zhong;
        int size=nums1.size();
        if(size%2==0)
        {
            zhong=(double)(nums1[size/2-1]+nums1[size/2])/2;
        }
        else
        {
            zhong=nums1[size/2];
        }
        return zhong;

    }
};

第二種 二分查找
思路就是不用歸并兩個(gè)數(shù)組，直接在兩個(gè)數(shù)組里找中間那個(gè)的數(shù)
具體思路還沒太懂 先貼個(gè)代碼

class Solution {
public:
    int findk(const vector<int>& nums1,const vector<int>& nums2,int k)
    {
        int m=nums1.size(),n=nums2.size();
        int index1=0,index2=0;

        while(true)
        {
            if(index1==m)
            return nums2[index2+k-1];
            if(index2==n) 
            return nums1[index1+k-1];
            if(k==1)
            return min(nums1[index1],nums2[index2]);

            int newindex1=min(index1+k/2-1,m-1);
            int newindex2=min(index2+k/2-1,n-1);
            int pivot1=nums1[newindex1];
            int pivot2=nums2[newindex2];

            if(pivot1<=pivot2)
            {
                k-=newindex1-index1+1;
                index1=newindex1+1;
            }
            else
            {
                k-=newindex2-index2+1;
                index2=newindex2+1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totallength=nums1.size()+nums2.size();
        if(totallength%2==1)
        {
            return findk(nums1,nums2,(totallength+1)/2);
        }
        else{
            return (findk(nums1,nums2,totallength/2+1)+findk(nums1,nums2,totallength/2))/2.0;
        }
    }
};