Problem
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:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Understanding
Median, 在统计学中叫做中位数，能够将一个数列分成不包含其自身的两个部分，两个部分长度相等。如果是处理一个有序数组，则如果数组长度为奇数，则取中间位，如果为偶数则取中间两数的均值。
测试用例
[1,3]
[2,3]
2.5
[1,10]
[2,3]
2.5
解法
归并排序通过合并两个有序的数列得到一个新有序数列，这就是解法的思想。然后取中间的一位或者两位的均值。
不过，与归并排序的不同的是，并不需要实际的合并，只需要找到最后数组的中间一位或者两位数即可。使用两个变量last,cur来记录即可。
空间复杂度O(1), 时间复杂度O(m+n)
代码(C++)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
const int length=nums1.size()+nums2.size();
const int indexEnd=(length%2==0)?(length+1)/2:length/2;
int i1=0,i2=0;
int index=0;
int cur,last;
while(i1 < nums1.size() && i2<nums2.size() && index <=indexEnd )
{
index++;
last=cur;
if(nums1[i1]>nums2[i2])
cur=nums2[i2++];
else
cur=nums1[i1++];
}
while(i1 < nums1.size() && index <=indexEnd)
{
last=cur;
cur=nums1[i1++];
index++;
}
while(i2 < nums2.size() && index <= indexEnd)
{
last=cur;
cur=nums2[i2++];
index++;
}
return length%2==0?(last+cur)/2.0:cur;
}
};
