4.Median of Two Sorted Arrays

这个题好难，主要是有时间复杂度 O(log(m+n)) 的限制。

思路：
把问题转化成求两个数组中求第K小的数即可。
用分治法，若A[k/2-1] >B[k/2-1] （即A的第k/2个数大于B的第k/2个数），则第K小的数不在B的前k/2个数中，同理B>A。
由此，每进行比较一次，都会有k/2个数被筛选下去，一直到最后就可以找到了。

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int k = nums1.size() + nums2.size();
        if(k%2==0) return ( findKth(nums1,0,nums2,0,k/2) + findKth(nums1,0,nums2,0,k/2+1)) / 2.0;
        else return findKth(nums1,0,nums2,0,k/2+1);
    }
    
    int findKth(vector<int>& nums1,int i,vector<int>& nums2,int j,int k){
        if(i >= nums1.size()) return nums2[j + k-1];
        if(j >= nums2.size()) return nums1[i + k-1];
        if(k == 1) return min(nums1[i],nums2[j]);
        int a = i+k/2-1 >= nums1.size() ? INT_MAX :nums1[i+k/2-1]; 
        int b = j+k/2-1 >= nums2.size() ? INT_MAX:nums2[j+k/2-1];
        if(a >= b) return findKth(nums1,i,nums2,j+k/2,k-k/2);
        else return findKth(nums1,i+k/2,nums2,j,k-k/2);
    }

注：开始智障了，没有用INT_MAX，用的是10000，结果没通过，还找了很久的bug.....

运行结果

太慢了，还可以进行优化的（数组的K/2位置的数字要不要去除）。等研究完最快的代码再来填坑。