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)).
Example1:

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example2:

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

解法一

解析

用一個(gè)新數(shù)組存放nums1和nums2合并后的數(shù)組。有序數(shù)組的合并最后取出中位數(shù)

還有種思路，就是遍歷兩個(gè)數(shù)組，在里面找到第i個(gè)大元素，但是時(shí)間復(fù)雜度為O（m+n）

代碼（C++）

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> numsAll;

        for (int i = 0, j = 0; i < nums1.size() || j < nums2.size();) {
            if (i < nums1.size()) {
                if (j < nums2.size()) {
                    if (nums1[i] < nums2[j]) {
                        numsAll.push_back(nums1[i++]);
                    } else {
                        numsAll.push_back(nums2[j++]);
                    }
                } else {
                    numsAll.push_back(nums1[i++]);
                }
            } else {
                numsAll.push_back(nums2[j++]);
            }
        }

        int middle = (nums1.size() + nums2.size()) >> 1;
        if ((nums1.size() + nums2.size()) % 2 == 1) {
            return (double)numsAll[middle];
        } else {
            return ((double)numsAll[middle] + (double)numsAll[middle-1]) / 2.0;
        }

    }
};