There are two sorted arrays nums1 and nums2 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)).
Example 1:
代码语言：javascript复制nums1 = [1, 3]
nums2 = [2]
The median is 2.0Example 2:
代码语言：javascript复制nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 3)/2 = 2.5想法题，但是也算不上hard难度，最优解法确实不太好想，刚开始想了一个二分的方法。
后来发现在最坏情况下，算法会退化为O(n m)，于是有了下面的想法：
每次把前K小的名额均分为两半，分到两个数组中，每组获得这个名额的最大数进行PK。
小的一方分到名额的数在下次分配中可以不考虑，因为已经可以确定他们必定属于前K小。
同时下一次剩余的未分配名额减去本次筛选掉的名额。
如此反复，直到最后只剩一个名额，或者某一组没有数。
在每一组数的个数大于k/2个时，这种方法每次都可以稳定筛选掉k/2个数，因而不论什么样的情况，效率都不会明显退化。
下面看代码：
代码语言：javascript复制class Solution
{
public:
double fun(vector<int> a,int sa,int ea,vector<int> b,int sb,int eb,int k)
{
if(ea 1-sa>eb 1-sb) //确保a的长度小于b，这样只用考虑a不足k/2的情况
return fun(b,sb,eb,a,sa,ea,k);
if(ea 1-sa == 0)//a中没有元素，返回b中第k大
return b[k-1];
if(k==1)//只剩一个名额
return min(a[sa],b[sb]);
int ta=min(ea 1-sa,k/2),tb=k-ta;//因为不知道较小的a会占用k/2还是自身长度的名额，所以作减法
if(a[sa ta-1]==b[sb tb-1])//相等时，这两个数就是所求值
return a[sa ta-1];
if(a[sa ta-1]>b[sb tb-1])//舍去较小的一部分
return fun(a,sa,ea,b,sb tb,eb,k-tb);
return fun(a,sa ta,ea,b,sb,eb,k-ta);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
int len1=nums1.size();
int len2=nums2.size();
if((len1 len2)%2)//奇数一个值，偶数两个值均值
return fun(nums1,0,len1-1,nums2,0,len2-1,(len1 len2 1)/2);
else
return (fun(nums1,0,len1-1,nums2,0,len2-1,(len1 len2)/2 1) fun(nums1,0,len1-1,nums2,0,len2-1,(len1 len2)/2))/2;
}
};
