兩個正序數(shù)組的中位數(shù)

描述

給定兩個大小為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。請你找出并返回這兩個正序數(shù)組的中位數(shù)。

進階：你能設計一個時間復雜度為 O(log (m+n)) 的算法解決此問題嗎？

示例1

輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數(shù)組 = [1,2,3] ，中位數(shù) 2

示例2

輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并數(shù)組 = [1,2,3,4] ，中位數(shù) (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

條件

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */

方法

1. 暴力法

比較好理解，就是合并數(shù)組，然后sort排序。
按題目要求，合并的數(shù)組長度是奇數(shù)時找出中間數(shù)，偶數(shù)時找出中間兩個數(shù)并求平均數(shù)。
代碼如下

var findMedianSortedArrays = function(nums1, nums2) {
  let allNums = nums1.concat(nums2)
  let sortAllNums = allNums.sort((a, b) => a - b) // 排序后的
  if (sortAllNums.length % 2) { // 奇數(shù)
    return sortAllNums[(sortAllNums.length - 1) / 2]
  } else { // 偶數(shù)
    return (sortAllNums[sortAllNums.length / 2] + sortAllNums[sortAllNums.length / 2 - 1]) / 2
  }

2. 二分法

本文主要講二分法，因為題目的進階要求是時間復雜度為 O(log (m+n))。這種時間復雜度有對數(shù)的時候，一般都要想到用二分法來處理這個問題。

首先，我們規(guī)定數(shù)組A的長度為m，數(shù)組B的長度為n，且m <= n。這里我們以小的數(shù)組做2分。

對于A數(shù)組，以l代表分割線位置,分割線左范圍值l0 = 0置，分割線右范圍值li = m。那么分割線位置i應該是 (l0 + li) / 2

那么數(shù)組A以 i 作二分，數(shù)組B以 j 作二分。那么根據(jù)題目的要求，i + j 要滿足等于 (m + n + 1) / 2 (編程語言向下取整)。

20201107213428.jpg

那么所得的分各項兩邊的數(shù)需要滿足如下條件：

1. Ai < Bj+1

2. Bj < Ai+1

滿足上述條件，再根據(jù)m + n的奇偶性求出中位數(shù)。

如果不滿足上述條件，說明分割線的位置錯誤。需要重新利用二分法二分剩下的位置，去尋找合適的分割線。

如果Ai > Bj+1 A數(shù)組分割線左邊大了，說明分割線太靠右了，需要向左移動。將分割線右范圍值在目前分割線的基礎上向左移動一位。li = i - 1。

如果Bj > Ai+1 A數(shù)組右邊小了，說明分割線太靠左了，需要向右移動，將分割線左范圍在原來基礎上向右移動一位。l0 = i + 1。

那么 i = (l0 + li) / 2; j = (m + n + 1) - i。

推理過程如下圖:

過程圖

過程圖

代碼

const findMedianSortedArrays  = (nums1, nums2) => {
  // 確保第一個數(shù)組長度較小
  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 = 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]

    // 判斷上面4個數(shù)的關系
    if (maxLeftA <= minRightB && minRightA >= maxLeftB) { // 滿足條件
      // 判斷奇偶性 然后得出結果
      return (m + n) % 2 === 1 ? Math.max(maxLeftA, maxLeftB) : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2
    }
    if (maxLeftA > minRightB) { // 分割線需要左移動
      high = i - 1
    }
    if (minRightA < maxLeftB) { // 分割線需要右移動
      low = i + 1
    }
  }
}

本文參考資料為leetCode的清華大佬l(wèi)ucifer