4. Median of Two Sorted Arrays

[Tcdian]

4. Median of Two Sorted Arrays

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

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

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

Example 1

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

The median is 2.0

Example 2

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

The median is (2 + 3)/2 = 2.5

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
    const len1 = nums1.length;
    const len2 = nums2.length;
    const half = Math.ceil((len1 + len2) / 2);
    let left = 0;
    let right = len1;
    while(left < right) {
        const i = Math.ceil((left + right) / 2);
        const j = half - i;
        if (nums1[i - 1] > nums2[j]) {
            right = i - 1;
        } else {
            left = i;
        }
    }
    const i = left;
    const j = half - i;
    const nums1LeftMax = i === 0 ? -Infinity : nums1[i - 1];
    const nums2LeftMax = j === 0 ? -Infinity : nums2[j - 1];
    const nums1RightMin = i === len1 ? Infinity : nums1[i];
    const nums2RightMin = j === len2 ? Infinity : nums2[j];
    if ((len1 + len2) % 2 === 1) {
        return Math.max(nums1LeftMax, nums2LeftMax);
    } else {
        return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
    }
};