4. 寻找两个正序数组的中位数 (opens new window)

Description

Difficulty: 困难

Related Topics: 数组 (opens new window), 二分查找 (opens new window), 分治 (opens new window)

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

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10⁶ <= nums1[i], nums2[i] <= 10⁶

Solution

Language: JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 * 1.二分查找
 * m+n 偶数 (m+n)/2 = (m+n+1)/2
 * m+n 奇数 (m+n+1)/2
 * i nums1 左边的个数
 * j nums2 左边的个数
 * 中位数大小 l[size] = (m+n+1)/2 = i + j
 * 
 * 分割线左边的所有元素需要满足的个数
 * left = 0, right = m
 * i = left + (right - left + 1) / 2
 * j = totalLeft - i
 * 
 * nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]
 * 获取左边最大值，右边最小值
 * 
 * 分奇数 偶数
 * 
 * 不符合条件，在 nums1 的区间 [0, m] 里查找恰当的分割线
 * 
 */
var findMedianSortedArrays = function(nums1, nums2) {
 if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1)

 const [m, n] = [nums1.length, nums2.length]
 let [left, right, min, max] = [0, m, -Infinity, Infinity]

 while (left <= right) {
  const i = (left + right) >>> 1
  const j = ((m+n+1) >> 1) - i

  const L1 = !i ? min : nums1[i-1]
  const L2 = !j ? min : nums2[j-1]
  const R1 = i === m ? max : nums1[i]
  const R2 = j === n ? max : nums2[j]
  
  if (L1 <= R2 && L2 <= R1) {
   const leftMax = Math.max(L1, L2)
   const rightMin = Math.min(R1, R2)
   return (m+n)%2 === 1 ? leftMax : (leftMax + rightMin) / 2
  }

  L1 > R2 ? right = i - 1 : left = i + 1
 }
};