Median of Two Sorted Arrays

Hard

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

Solution

题目的意思是找出两个有序数组的中位数,并要求算法的时间复杂度为$O(\log (m+n))$

如果采用先合并成一个大数组再排序的方式,找出中位数。并不能满足时间复杂度的要求,虽然提交结果可能会显示通过。

var findMedianSortedArrays = function (nums1, nums2) {
    let nums = nums1.concat(nums2).sort((a, b) => a - b)
    let res
    if (nums.length % 2 == 0) {
      res = (nums[parseInt((nums.length - 1) / 2)] + nums[parseInt((nums.length - 1) / 2 + 1)]) / 2
    } else {
      res = nums[parseInt(nums.length / 2)]
    }
    return res
}

为了满足$O(\log (m+n))$时间复杂度的要求可以使用二分搜索的算法。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  let n1 = nums1.length
  let n2 = nums2.length
  if (n1 > n2) {
    return findMedianSortedArrays(nums2, nums1)
  }
  let middle = parseInt((n1 + n2 + 1) / 2)
  
  let left = 0
  let right = n1
  while (left < right) {
    let m1 = parseInt(left + (right - left) / 2)
    let m2 = middle - m1
    if (nums1[m1] < nums2[m2 - 1])
      left = m1 + 1
    else
      right = m1
  }
  let m1 = left
  let m2 = middle - left

  let  med1= Math.max(m1 <= 0 ? -Number.MAX_VALUE : nums1[m1 - 1], m2 <= 0 ? -Number.MAX_VALUE : nums2[m2 - 1])

  if ((n1 + n2) % 2 === 1) {
    return med1
  }
  let med2 = Math.min(m1 >= n1 ? Number.MAX_VALUE : nums1[m1], m2 >= n2 ? Number.MAX_VALUE : nums2[m2])
  return (med1 + med2) * 0.5;
}