Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
求两个数组合并后的中位数
Algorithm：
中位数求法：把长度为k数组从小到大排列，返回中间位置的元素。
k为奇数，中位数为nums[k/2]，k为偶数中位数为(nums[k/2]+nums[(k/2)⑴]/2
算法1：归并两个数组后，找中位数，复杂度O(m+n)
算法2：类似2分查找，不需要归并，复杂度O(log(m+n))
现在详细说明解法2，我们可以把问题转化为寻觅第k大的元素
假定AB的长度都大于k/2，比较A[(k/2)⑴]和B[(k/2)⑴]，有3种情况
1、A[k/2⑴] = B[k/2⑴]
此时，我们就已找到第k大的元素，即element=A[k/2⑴]=B[k/2⑴]
2、A[k/2⑴] < B[k/2⑴]
此时，意味着A[0]~A[k/2⑴]都比第k个元素小，由于A[0]~A[k/2⑴]有k/2个元素，B[0]~B[k/2⑴]有k/2个元素，如果A[k/2⑴]是比第k个元素还大的元素，假定A[k/2⑴]是比第k+1小的元素，那末B[k/2⑴]最少是第k+2大的元素。但是在A中最多有k/2⑴个元素小于A[k/2⑴]，在B中最多有k/2⑴个元素小于A[k/2⑴]，总共最多有(k/2⑴+k/2⑴)即k⑵个元素。所以A[k/2⑴]不可能大于第k个元素。所以我们可以删去，然后找第k-k/2=k/2个元素。
3、A[k/2⑴] > B[k/2⑴]
类似2
在这里要注意3种特殊情况
1、如果AB有1个是空，则返回非空数组下标为k⑴的元素，即A[k⑴]或B[k⑴]
2、如果k==1，则返回min{A[0],B[0]}
3、如果k/2比短的数组长的话（假定是A），则比较A[m⑴]和B[k/2⑴]
Ex:
A{1,3,7,8} m1=4
B{2,4,5,6,7,8,9,10,12} m2=9
由于删除元素较为麻烦，所以在程序中设两个变量begin1，begin2作为起始元素。再设置m1和m2作为有效数组长度。
1、合并后的数组，长度为m1+m2=13，那末我们要找出第13/2+1=7，即k=7，第7大的元素。刚开始begin1和begin2都为0，m1=4，m2=9
2、A[begin1+k/2⑴]=A[2]=7 > B[begin2+k/2⑴]=B[2]=5，所以我们删去B中的2，4，5，在程序中，我们可使begin2指针指向元素6，即begin2=3，m2=9⑶=6，现在我们要找出k⑶即第4大的元素
3、k=4，begin1=0，begin2=3，m1=4，m2=6，A[begin1+k/2⑴]=A[1]=3 < B[begin2+k/2⑴]=B[7]，所以我们删去A中1，3，begin1=0+2=2，m1=4⑵=2，现在我们要找出k⑵，即第2大的元素
4、k=2，begin1=2，begin2=3，m1=2，m2=6，A[begin1+k/2⑴]=A[2]=7 > B[begin2+k/2⑴]=B[3]=6，所以我们删去B中6，begin2=3+1=4，m2=6⑴=5，现在我们要找出k⑴，即第1大的元素
5、k=1，begin1=2，begin2=4，m1=2，m2=5比较A[begin1]=A[2]=7,B[begin2]=B[4]=7，返回7，终究结果为7
Accepted Code：
算法1：
class Solution {
public:
vector<int> MergeSort(vector<int>& nums1, vector<int>& nums2)
{
vector<int> res;
int i=0,j=0;
while(i<nums1.size() && j<nums2.size())
{
if(nums1[i]<=nums2[j])
{
res.push_back(nums1[i]);
i++;
}
else
{
res.push_back(nums2[j]);
j++;
}
}
while(i<nums1.size())
{
res.push_back(nums1[i]);
i++;
}
while(j<nums2.size())
{
res.push_back(nums2[j]);
j++;
}
return res;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> temp=MergeSort(nums1,nums2);
double res;
int len=temp.size();
if(temp.size()%2==0)
res=(double)(temp[len/2]+temp[(len/2)⑴])/2;
else
res=temp[len/2];
return res;
}
};
算法2：
class Solution {
public:
double find_kth(vector<int>& nums1,vector<int>& nums2,int m1,int m2,int k,int begin1,int begin2)
{
if(m1 > m2)
return find_kth(nums2,nums1,m2,m1,k,begin2,begin1);
if(m1 == 0)
return nums2[k⑴];
if(k == 1)
return nums1[begin1] < nums2[begin2]?nums1[begin1]:nums2[begin2];
int a=min(k/2,m1); //the ath element in A
int b=k-a; //the bth element in B
if(nums1[begin1+a⑴] < nums2[begin2+b⑴]) //compare the ath element in A and the bth element in B
return find_kth(nums1,nums2,m1-a,m2,k-a,begin1+a,begin2);
else
return find_kth(nums1,nums2,m1,m2-b,k-b,begin1,begin2+b);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m1=nums1.size();
int m2=nums2.size();
int k=(m1+m2)>>1;
if((m1+m2)%2==1)
return find_kth(nums1,nums2,m1,m2,k+1,0,0);
else
return (find_kth(nums1,nums2,m1,m2,k+1,0,0)+find_kth(nums1,nums2,m1,m2,k,0,0))/2;
}
};
