4. 寻找两个正序数组的中位数.md

思路

二分法

代码

var findMedianSortedArrays = function(nums1, nums2) {
  const len1 = nums1.length, len2 = nums2.length;
  let left = (len1 + len2 + 1) >> 1, right = (len1 + len2 + 2) >> 1
  return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0
};

function findKth(nums1, i, nums2, j, k) {
  // nums1 全部排除掉了
  if (i >= nums1.length) return nums2[j+k-1]
  // nums2 全部排除掉了
  if (j >= nums2.length) return nums1[i+k-1]
  // 递归出口
  if (k == 1) return Math.min(nums1[i], nums2[j])
  // 两个数组的第 k/2 小的数字，若不足则赋值最大，以便淘汰另一数组的前k/2个
  let mid1 = (i + (k >> 1) - 1 < nums1.length) ? nums1[i + (k >> 1) - 1] : Number.MAX_SAFE_INTEGER
  let mid2 = (j + (k >> 1) - 1 < nums2.length) ? nums2[j + (k >> 1) - 1] : Number.MAX_SAFE_INTEGER
  if (mid1 < mid2) {
    return findKth(nums1, i + (k >> 1), nums2, j, k - (k >> 1))
  } else {
    return findKth(nums1, i, nums2, j+ (k >> 1), k - (k >> 1))
  }
}

复杂度分析

时间复杂度 $O(log(M+N))$

空间复杂度 $O(1)$