给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
示例 1:
nums1[1,3]
nums2[2]
中位数：2.0
示例 2:
nums1[1,2]
nums2[2,3]
中位数:(2+2)/2=2.0
思路：
因为是两个已经有序的数组，要求中位数，只需要将两个数组合并成一个有序数组，然后根据数组元素个数的奇偶性，分开来便可以求出中位数,若最后合并成功的数组名为K的话，（偶数的话中位数=K[(N/2)]+K[(N/2-1)]/2）(奇数的话中位数=K[(N/2)])。并且题目要求时间复杂度为O(log(M+N)),所以在排序的时候，要考虑时间复杂度。
代码实现（c++）：
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int i=0,j=0;
int N1 = nums1.size();
int N2 = nums2.size();
vector<int> count;
while(i<N1 || j<N2)
{
if(i>=N1)
{
count.push_back(nums2[j++]);
continue;
}
if(j>=N2)
{
count.push_back(nums1[i++]);
continue;
}
if(nums1[i]<nums2[j])
{
count.push_back(nums1[i++]);
}
else
{
count.push_back(nums2[j++]);
}
}
if((N1+N2)%2==0)
{
return (double)(count[(N1+N2)/2]+count[(N1+N2)/2-1])/2;
}
else
{
return (double)count[(N1+N2)/2];
}
}
};