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;
    }
};