Leetcode04
问题：求两个以排序序列的中位数。 为了更好的运用分治，将问题转化为求第k小的数。 转化后：两个长度分别为m,n的有序序列，如果m+n为偶数，求第(m+n)/2小的数和第(m+n)/2+1小的数的平均数；否则求第(m+n)/2+1小的数。 首先处理递归边界和特殊情况：
假设第一个序列vec1的长度小于第二个序列vec2，如果不是这样，就调换位置重新递归。 如果第一个序列vec1为空，那么直接返回第二个序列的第k小的数。 如果k为1，也就是求最小的数，那么直接返回vec1[0],vec2[0]中小的那个。
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int k=nums1.size()+nums2.size();
if(k%2==0)
return (median(nums1,nums2,k/2)+median(nums1,nums2,k/2+1))/2.0;
else return median(nums1,nums2,k/2+1);
}
double median(vector<int>& vec1,vector<int>& vec2,int k){
if(vec1.size()>vec2.size()) return median(vec2,vec1,k);
if(vec1.empty()) return vec2[k-1];
if(k==1) return min(vec1[0],vec2[0]);
int p1=vec1.size()>k/2?k/2:vec1.size();
int p2=k-p1;
if(vec1[p1-1]>vec2[p2-1]){
vector<int> vec(vec2.begin()+p2,vec2.end());
return median(vec1,vec,k-p2);
}
else if(vec1[p1-1]<vec2[p2-1]){
vector<int> vec(vec1.begin()+p1,vec1.end());
return median(vec,vec2,k-p1);
}
else return vec1[p1-1];
}