4. 两个排序数组的中位数

[funnycoderstar]

题目描述

给定两个大小为 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

解题方法

1. O(nlogn)

将两个数组合并成一个, 然后排序(JavaScript数组内置的sort函数), 复杂度O(nlogn), 最后根据数组的长度选择中位数

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const nums = nums1.concat(nums2);
    nums.sort(function(a, b) {
        return a - b;
    });
    let len = nums.length;
    if (len % 2 === 0) {
        return (nums[len / 2] + nums[len / 2 - 1]) / 2;
    } else {
        return nums[(len - 1) / 2];
    }
};

2. O(n)

将两个有序的数组合并成一个有序的数组, 每个数组都已经是单独排过序的, 使用归并排序封装一个merge函数, 剩下思路上上述一样

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
    const merge = function (left, right) {
        var temp = [];
        while (left.length && right.length) {
            if (left[0] < right[0]) {
                temp.push(left.shift());
            } else {
                temp.push(right.shift());
            }
        }
        return temp.concat(left, right);
    };
    let nums = merge(nums1, nums2);
    let len = nums.length;
    if (len % 2 === 0) {
        return (nums[len / 2] + nums[len / 2 - 1]) / 2;
    } else {
        return nums[(len - 1) / 2];
    }
};