4.LeetCode（寻找两个正序数组的中位数）——JavaScript

超、凢脫俗 2022-12-26 08:15 178阅读 0赞

## 题目描述 ##

[原题链接][Link 1]

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

**进阶**：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

示例 1：

输入：nums1 = [1,3], nums2 = [2]
    输出：2.00000
    解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
    输出：2.50000
    解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
    输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
    输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
    输出：2.00000

**提示：**

*  nums1.length == m
 *  nums2.length == n
 *  0 <= m <= 1000
 *  0 <= n <= 1000
 *  1 <= m + n <= 2000
 *  \-106 <= nums1\[i\], nums2\[i\] <= 106

## 我的解法 ##

/**
     * @param {number[]} nums1
     * @param {number[]} nums2
     * @return {number}
     */
    var findMedianSortedArrays = function(nums1, nums2) {
        
        var len1 = nums1.length;
        var len2 = nums2.length;
        var nums2Index = 0;
        var arr = nums1;
        for (var i = 0; i < len2; i++) {
        
            var j = 0;
            while (j < len1) {
        
                if (arr[j] > nums2[i]) {
        
                    arr.splice(j, 0, nums2[i]);
                    nums2Index++;
                    len1++;
                    break;
                }
                j++;
            }
        }
    
        if (nums2Index < len2) {
        
            for (var i = nums2Index; i < len2; i++) {
        
                arr.push(nums2[i]);
                len1++;
            }
        }
        var result = (arr[Math.floor((len1 - 1) / 2)] + arr[Math.ceil((len1 - 1) / 2)]) / 2;
        return len1 ? result : 0;
    };

## 更优解法 ##

/**
     * 二分解法
     * @param {number[]} nums1
     * @param {number[]} nums2
     * @return {number}
     */
    var findMedianSortedArrays = function(nums1, nums2) {
        
      // make sure to do binary search for shorten array
      if (nums1.length > nums2.length) {
        
        [nums1, nums2] = [nums2, nums1]
      }
      const m = nums1.length
      const n = nums2.length
      let low = 0
      let high = m
      while(low <= high) {
        
        const i = low + Math.floor((high - low) / 2)
        const j = Math.floor((m + n + 1) / 2) - i
    
        const maxLeftA = i === 0 ? -Infinity : nums1[i-1]
        const minRightA = i === m ? Infinity : nums1[i]
        const maxLeftB = j === 0 ? -Infinity : nums2[j-1]
        const minRightB = j === n ? Infinity : nums2[j]
    
        if (maxLeftA <= minRightB && minRightA >= maxLeftB) {
        
          return (m + n) % 2 === 1
            ? Math.max(maxLeftA, maxLeftB)
            : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2
        } else if (maxLeftA > minRightB) {
        
          high = i - 1
        } else {
        
          low = low + 1
        }
      }
    };

[Link 1]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays