题目描述

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

样例

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

算法1

(暴力枚举) $O(n)$

这题最骚的一点是要求用$O(nlogn)$的算法，不过我做出来的算法貌似是$O(n)$的，就很奇怪。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 1. 把两个数组变成一个数组
        int n1 = nums1.size();
        int n2 = nums2.size();

        vector<int> res;

        int i1 = 0;
        int i2 = 0;

        while (i1 < n1 && i2 < n2){
            if (nums1[i1] < nums2[i2]){
                // 把两个数据合并起来
                res.push_back(nums1[i1]);
                i1 ++;
            }else{
                res.push_back(nums2[i2]);
                i2 ++;
            }
        }
        // cout << "i1 = " << i1 << endl;
        // cout << "i2 = " << i1 << endl;

        if (i1 < n1){
            for (int i = i1; i < n1; i ++){
                res.push_back(nums1[i]);
            }
        }

        if (i2 < n2){
            for (int i = i2; i < n2; i ++){
                res.push_back(nums2[i]);
            }
        }

        // for (int c : res){
        //     cout << c << endl;
        // }
        int size = res.size();
        if (size % 2){
            // 奇数个
            return res[size/2];
        }else{
            return ((float)(res[size/2] + res[size/2-1])) / 2.0;
        }
        return 0;

    }
};