兩個正序數(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 作二分缭贡。那么根據題目的要求炉擅，i + j 要滿足等于 (m + n + 1) / 2 (編程語言向下取整)。
那么所得的分各項兩邊的數(shù)需要滿足如下條件：
Ai < Bj+1
Bj < Ai+1
滿足上述條件阳惹，再根據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
}
}
}
