4. 寻找两个正序数组的中位数

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

示例 2：

示例 3：

示例 4：

示例 5：

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

解答（C++）

方法一

思路：依据从小到大的顺序依次拼接为一个新的正序数组

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        vector<int> a(m+n);
        int i = 0;
        int j = 0;
        int k = 0;
        while(i < m && j < n) {
            if(nums1[i] < nums2[j]) {
                a[k] = nums1[i];
                ++i;
            } else {
                a[k] = nums2[j];
                ++j;
            }
            ++k;
        }
        while(i < m) {
            a[k] = nums1[i];
            ++i;
            ++k;
        }
        while(j < n) {
            a[k] = nums2[j];
            ++j;
            ++k;
        }
        if((m+n)%2 == 1) return a[(m+n)/2];
        return double((a[(m+n)/2]+a[(m+n)/2-1])/2.0);
    }
};

解答（Python）