第四题 - 寻找两个正序数组的中位数

[laizimo]

题目描述

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

算法

二分查找

答案

图解：

代码：

/**
 * 二分查找
 */
function Max(nums1, nums2) {
    //比较两个数，不存在的情况
    if (!nums1) return nums2;
    if (!nums2) return nums1;
    return nums1 > nums2 ? nums1 : nums2;
}

function Min(nums1, nums2) {
    // 比较两个数，不存在的情况
    if (!nums1) return nums2;
    if (!nums2) return nums1;
    return nums1 > nums2 ? nums2 : nums1;
}
var findMedianSortedArrays = function(nums1, nums2) {
    // 比较数组大小，将长度短的放在前面
    if (nums1.length > nums2.length) {
        let temp = nums1;
        nums1 = nums2;
        nums2 = temp;
    }

    const len1 = nums1.length, len2 = nums2.length;
    let i = Math.floor(len1 / 2), j = Math.ceil(len2 / 2);
    let beforeI = 0;

    while(true) {
        //#2 比较 A[i - 1] <= B[j] 和 B[j - 1] <= A[i]是否成立，成立就产生中位数
        if (
            (nums1[i - 1] === undefined || nums2[j] === undefined || nums1[i - 1] <= nums2[j]) &&
            (nums1[i] === undefined || nums2[j - 1] === undefined || nums2[j - 1] <= nums1[i])
        ) {
            //#3 取两边的数量
            const left = i + j, right = len1 + len2 - i - j;
            //#4 如果左边数量 === 右边数量，取左边最大数 + 右边最小数
            if (left === right) return (Max(nums1[i - 1], nums2[j - 1]) + Min(nums1[i], nums2[j])) / 2;
            //#5 左边数量 < 右边数量，取右边最小数
            if (left < right) return Min(nums1[i], nums2[j]);
            //#6 左边数量 > 右边数量，取左边最大数
            if (left > right) return Max(nums1[i - 1], nums2[j - 1]);
        } else if (nums1[i - 1] > nums2[j]) {
            //#7 仅满足A[i - 1] > B[j], i左移，j右移
            let step = Math.max(Math.floor((i - beforeI) / 2), 1);
            beforeI = i;
            i -= step;
            j += step;
            continue;
        } else if (nums2[j - 1] > nums1[i]) {
            //#8 仅满足 B[j - 1] > A[i], i右移，j左移
            let step = Math.max(Math.floor((i - beforeI) / 2), 1);
            beforeI = i;
            i += step;
            j -= step;
            continue;
        }
    }
};