给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
思路
先做归并排序，然后求中位数
代码
class Solution {
public:
void mergeSort(vector<int>& v)
{
int size=v.size();
if(size<=1) return;
vector<int> v1=vector<int>(v.begin(),v.begin()+size/2);
vector<int> v2=vector<int>(v.begin()+size/2,v.end());
mergeSort(v1);
mergeSort(v2);
merge(v,v1,v2);
}
void merge(vector<int>& v,vector<int>& v1,vector<int>& v2)
{
vector<int> index={0,0};
for(int i=0;i<v.size();i++)
{
if(index[0]==v1.size())
{
v[i]=v2[index[1]];
index[1]++;
continue;
}
else if(index[1]==v2.size())
{
v[i]=v1[index[0]];
index[0]++;
continue;
}
if(v1[index[0]]<v2[index[1]])
{
v[i]=v1[index[0]];
index[0]++;
}
else
{
v[i]=v2[index[1]];
index[1]++;
}
}
return;
}
double findMedianSortedArrays(vector<int>& nums1,vector<int>& nums2)
{
int length=nums1.size()+nums2.size();
vector<int> merged(length,0);
mergeSort(nums1);
mergeSort(nums2);
merge(merged,nums1,nums2);
if(length%2)
return merged[length/2];
else
return (merged[length/2-1]+merged[length/2])/2.0;
}
};