4. Median of Two Sorted Arrays

题目如下所示：

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

实现的算法比较弱智就是将两个数组归并并找出中间位置的那个数字。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int size1 = nums1.size();
        int size2 = nums2.size();
        int two = ((size1 + size2) % 2 == 1) ? 0 : 1;
        if (size1 > size2) {
            vector<int> nums = nums1;
            nums1 = nums2;
            nums2 = nums;
        }
        size1 = nums1.size();
        size2 = nums2.size();

        if (size1 == 0 && size2 != 0) {
            if (two) return (nums2[size2 / 2] + 
                nums2[size2 / 2 - 1]) / 2.0;
            else return nums2[size2 / 2];
        }
        else if (size2 == 0) {
            return 0.0;
        }
        else {
            vector<int> nums(size1 + size2);
            int i = 0;
            int j = 0;
            int index = 0;
            int nu1 = 0;
            int nu2 = 0;
            for (int index = 0; index < (size1 + 
                    size2); index++) {
                nu1 = (i < size1) ? nums1[i] : INT_MAX;
                nu2 = (j < size2) ? nums2[j] : INT_MAX;
                if (nu1 < nu2) {
                    nums[index] = nums1[i];
                    i++;
                }
                else if (nu1 > nu2) {
                    nums[index] = nums2[j];
                    j++;
                }
                else if (nu1 == nu2) {
                    nums[index] = nums1[i];index++;
                    nums[index] = nums2[j];
                    i++;
                    j++;
                }
            }
            if ((size1 + size2) % 2 == 1)
                return nums[(size1 + size2) / 2];
            else
                return (nums[(size1 + size2) / 2] + 
                nums[(size1 + size2) / 2 - 1]) / 2.0;
        }

    }
};

使用这种方法的话，算法的时间复杂度是O(m + n),空间复杂度也是O(m + n).