4.html

<script>
    /*
        取最中间的两个数值的平均数作为中位数
        给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
        请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
        你可以假设 nums1 和 nums2 不会同时为空。
        https://leetcode-cn.com/problems/median-of-two-sorted-arrays
         递归二分
         复杂度 O(log(min(m,n)))
         * @param {number[]} nums1
         * @param {number[]} nums2
         * @return {number}
         */
    var findMedianSortedArrays = function (nums1, nums2) {
        let nums1_len = nums1.length;
        let nums2_len = nums2.length;
        // 使nums1长度比nums2小
        if (nums1_len > nums2_len) {
            return findMedianSortedArrays(nums2, nums1);
        }
        // 计算合并数组被中位数分割后 前/后的元素个数 -> 中位数 = (max(前)+min(后))/2
        let k = Math.floor((nums1_len + nums2_len) / 2);
        let left = 0;
        let right = nums1_len;
        let mid1, mid2;
        while (left <= right) {
            // 对 A数组 left-right区间 切分 取该区间的中位数索引,将该索引计入后区间
            mid1 = Math.floor((left + right) / 2);
            // 倒推出B数组分割后的前区间元素个数,将mid2计入后区间
            mid2 = k - mid1;
            if (nums1[mid1] < nums2[mid2 - 1]) {
                // 如果A-min(后) < B-max(前) 说明A-前区间分少了 缩小left区间尝试下一次切分
                left = mid1 + 1;
            } else if (nums1[mid1 - 1] > nums2[mid2]) {
                // 如果A-max(前) > B-min(后) 说明A-前区间分多了 缩小right区间尝试下一次切分
                // 如果A数组中位数 比 反推的B数组中位数大, 则表示
                right = mid1 - 1;
            } else {
                // A-min(后) >= B-max(前) && A-max(前) <= B-min(后) 切割成功
                if ((nums1_len + nums2_len) % 2 === 1) {
                    // 为奇数,应取后区间的最小值
                    return Math.min(mid1 < nums1_len ? nums1[mid1] : Number.MAX_SAFE_INTEGER, mid2 < nums2_len ? nums2[mid2] : Number.MAX_SAFE_INTEGER);
                } else {
                    // 长度为偶数 取A-max(前) 与 B-max(前) 的最大值为第一个中位数
                    let first_mid = Math.max(mid1 > 0 ? nums1[mid1 - 1] : Number.MIN_SAFE_INTEGER, mid2 > 0 ? nums2[mid2 - 1] : Number.MIN_SAFE_INTEGER);
                    // 取A-min(后) 与 B-min(后) 的最小值为第二个中位数 求平均数
                    let second_mid = Math.min(mid1 < nums1_len ? nums1[mid1] : Number.MAX_SAFE_INTEGER, mid2 < nums2_len ? nums2[mid2] : Number.MAX_SAFE_INTEGER);
                    return (first_mid + second_mid) / 2;
                }
            }
        }
    };

    /**
     * 复杂度 O(m+n+1)//2
     * @param nums1
     * @param nums2
     * @returns {number}
     */
    var findMedianSortedArrays1 = function (nums1, nums2) {
        // 根据两数组长度计算中位数后面有多少元素
        let total_len = nums1.length + nums2.length;
        let fetch_num = Math.floor((total_len - 1) / 2);
        // 获取最中间的第一个数
        for (let i = 0; i < fetch_num; i++) {
            popMax1(nums1, nums2);
        }
        // 如果只有一个数直接返回，否则取两个数 返回平均数
        if (total_len % 2 === 1) {
            return popMax1(nums1, nums2);
        } else {
            return 1.0 * (popMax1(nums1, nums2) + popMax1(nums1, nums2)) / 2;
        }
    };

    function popMax1(nums1, nums2) {
        let num2_len = nums2.length;
        if (num2_len === 0 || nums1[nums1.length - 1] > nums2[num2_len - 1]) {
            return nums1.pop();
        } else {
            return nums2.pop();
        }
    }

    console.log(findMedianSortedArrays([1, 2], [3, 4])); // 2.5
    console.log(findMedianSortedArrays([1, 2, 3], [3, 4, 5, 6, 7, 8, 9, 10])); // 5
</script>