LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数

题目描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

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

分析

算中位数，在我们平时的思路上， 就是把一组无序的数， 排序， 取位置在最中间的数，如果数组有偶数个数， 就取中间两个数的平均数

因此最容易想到的方法是， 把数组 nums1 和数组 nums2 合并起来， 然后使用sort()方法排序， 取中间数即可。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    // 合并
    let nums = nums1.concat(nums2)
    // 排序
    nums.sort(function(a, b) { return a-b })
    let l = nums.length
    // 偶数个 返回中间两数平均值
    if (l % 2 === 0) {
        return (nums[l / 2 - 1] + nums[l / 2]) / 2
    } else {
    // 奇数个 返回中间的数
        return nums[parseInt(l / 2)]
    }
};

但这样解其实是不符合题意的， 因为题目限定了时间复杂度为O(log(m + n))， 这是一个log级别的复杂度， 显然是不能使用任何排序算法的，这也是这个题目难度是困难的原因

这道题我是不会的， 因为我没有想到中位数另外一个定义：
将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

也就是说， 这是一种分而治之的思想， 如果num1长度为3， nums2长度为4， 我们可以从中间对nums1数组切一刀， 假设切一刀后, nums1左侧的元素个数为 1 个, 那么根据中位数定义中“将一个集合划分为两个长度相等的子集”，可以知道 ，此时num2左侧的元素个数一定要为 6， 因为只有这样切，才可以保证两边元素个数相等。

left      |        right
nums1[0], nums1[1], ..., nums1[i-1]  |  nums1[i], nums1[i+1], ..., nums1[m-1]
nums2[0], nums2[1], ..., nums2[j-1]  |  nums2[j], nums2[j+1], ..., nums2[n-1]

假设 L1 为 nums1 切面左侧的最后一个元素 num1[i - 1]， R2为 nums2切面右侧第一个元素nums[j]， 那么根据定义“其中一个子集中的元素总是大于另一个子集中的元素”可知 L1 一定要 小于 R2， 同理 L2一定要小于 R1， 如果不满足， 就要用到二分查找， 更新切面的位置，直到满足这两个定义：

• 两个长度相等的子集 即 分别切开后， nums1和nums2左侧元素个数和右侧元素个数要相等
• 其中一个子集中的元素总是大于另一个子集中的元素。即 L1 < R2, L2 < R1

寻找到满足条件的切点后， 计算中位数，如果是奇数个， 取nums1, nums2左侧较大的数， 右侧较小的数，取平均值 如果是偶数个， 取右侧较小值即为所求

Javascript解法

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
   var findMedianSortedArrays = function(nums1, nums2) {
   
    // 过滤边界情况
    let l1 = nums1.length, l2 = nums2.length
    if(l1 === 0 && l2 === 1) { return nums2[0] }
    if (l2 === 0 && l1 === 1) { return nums1[0] }
    if (l1 === 1 && l2 === 1) { return (nums1[0] + nums2[0]) / 2 }

     // 如果第一个数组长度大于第二个， 则把他们顺序颠倒 运行函数
     // 因为知道了nums1在哪儿切， 就知道了nums2在哪儿切， 因此选数组长度小的切节省时间
    if(nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1)
    }
    
   
    // 二分查找切点位置的左右边界
    let cutL = 0
    let cutR = nums1.length
    
    let cut1 = 0, cut2 = 0
    // 二分查找
    while(cutL <= cutR) {
    // 根据中位数的特征 两个数组合起来的中位数， 在数组的中间位置切开
   // 如果nums1 + nums2的总长度是5， 假设从nums1第二个位置切开，
   // nums1被切开的左侧有两个元素， 那么直接就可知道, 此时nums2在第三
   // 个位置被切开
        cut1 = parseInt((cutR - cutL) / 2) + cutL
        cut2 = parseInt((l1 + l2) / 2) - cut1
        // 分别计算切面两侧的元素L1, L2, R1, R2
        let L1 = (cut1 === 0) ? -Infinity : nums1[cut1 - 1]
        let L2 = (cut2 === 0) ? -Infinity : nums2[cut2 - 1]
        let R1 = (cut1 === l1) ? Infinity : nums1[cut1]
        let R2 = (cut2 === l2) ? Infinity : nums2[cut2]
        // 如果左侧大于了右侧， 说明该切点切得太靠后， 减少右边界
        if (L1 > R2) {
            cutR = cut1 - 1
        } else if (L2 > R1) {
            // 如果右侧大于左侧， 说明切点太靠前， 增加左边界
            cutL = cut1 + 1
        } else {
            // 当满足情况时， 取L1 L2中的最大的， R1,R2中最小的，即为合成后的数组的中间两数 如果数量为偶数个 返回均值
            if ((l1 + l2) % 2 === 0) {
                L1 = L1 > L2 ? L1 : L2
                R1 = R1 < R2 ? R1 : R2
                return (L1 + R1) / 2
            } else {
                // 如果是奇数个， 按照规律 直接返回R1 R2中的较大者即为所求
                R1 = R1 < R2 ? R1 : R2
                return R1
            }
        }
    }
    return -1
};

运行结果