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

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

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

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

示例 1:

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

则中位数是 2.0
示例 2:

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

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

思考

这题难度标记为困难，其实不要被难度标记吓到了
读完题目会发现还是比较简单的，思路很清晰
把两个有序数组合成一个有序数组，然后取中位数就可以了，而且时间复杂度也不高只需要一次遍历
也可以在合并遍历的时候就拿到中位数

代码

class Solution {
    public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> nums;
        int i = 0;
        int j = 0;
        for (; i < nums1.size(); i++) {
            bool addI = false;
            for (; j < nums2.size(); j++) {
                if (nums2[j] > nums1[i]) {
                    nums.push_back(nums1[i]);
                    addI = true;
                    break;
                }
                nums.push_back(nums2[j]);
            }
            if (!addI) {
                nums.push_back(nums1[i]);
            }
        }

        for (; j < nums2.size(); j++) {
            nums.push_back(nums2[j]);
        }

        if (nums.size() % 2 == 0) {
            return 1.0 * (nums[nums.size() / 2] + nums[nums.size() / 2 - 1]) / 2.0;
        } else {
            return nums[nums.size() / 2];
        }
    }
};