Description
給定兩個已排序的整數陣列
nums1和nums2，找出這兩個陣列合併後的中位數。要求時間複雜度為O(log(m + n))。
Example:
Input: nums1 = [1,3], nums2 = [2] Output: 2.0
Intuition#
在較短的陣列上二分搜尋「切割位置」，使得左半部的所有元素都小於等於右半部的所有元素。
- 中位數把合併後的陣列分成等長的左右兩半
- 我們不需要真的合併，只需要找到正確的「分割線」
- 在較短的陣列上二分搜尋分割位置，另一個陣列的分割位置可以直接算出來
- 驗證條件：左半部的最大值 <= 右半部的最小值
Approaches#
1: Merge and Find#
- 概念: 合併兩個陣列後直接取中位數
- 時間複雜度:
O(m + n) - 空間複雜度:
O(m + n)
Merge and Find 程式碼
class Solution {
fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
val merged = IntArray(nums1.size + nums2.size)
var i = 0; var j = 0; var k = 0
while (i < nums1.size && j < nums2.size) {
if (nums1[i] <= nums2[j]) merged[k++] = nums1[i++]
else merged[k++] = nums2[j++]
}
while (i < nums1.size) merged[k++] = nums1[i++]
while (j < nums2.size) merged[k++] = nums2[j++]
val mid = merged.size / 2
return if (merged.size % 2 == 0) {
(merged[mid - 1] + merged[mid]) / 2.0
} else {
merged[mid].toDouble()
}
}
}⭐2: Binary Search on Partition#
- 概念: 在較短陣列上二分搜尋分割位置，確保左半部最大值不超過右半部最小值
- 時間複雜度:
O(log(min(m, n))) - 空間複雜度:
O(1)
class Solution {
fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
// 確保在較短的陣列上二分搜尋
val a = if (nums1.size <= nums2.size) nums1 else nums2
val b = if (nums1.size <= nums2.size) nums2 else nums1
val m = a.size
val n = b.size
val half = (m + n + 1) / 2
var left = 0
var right = m
while (left <= right) {
val i = left + (right - left) / 2 // a 的分割位置
val j = half - i // b 的分割位置
val aLeft = if (i > 0) a[i - 1] else Int.MIN_VALUE
val aRight = if (i < m) a[i] else Int.MAX_VALUE
val bLeft = if (j > 0) b[j - 1] else Int.MIN_VALUE
val bRight = if (j < n) b[j] else Int.MAX_VALUE
if (aLeft <= bRight && bLeft <= aRight) {
// 找到正確的分割
return if ((m + n) % 2 == 0) {
(maxOf(aLeft, bLeft) + minOf(aRight, bRight)) / 2.0
} else {
maxOf(aLeft, bLeft).toDouble()
}
} else if (aLeft > bRight) {
right = i - 1
} else {
left = i + 1
}
}
return 0.0
}
}邊界處理是這題的難點：當分割位置在陣列的最左或最右時，需要用
Int.MIN_VALUE/Int.MAX_VALUE作為虛擬的邊界值。另外要確保始終在較短的陣列上二分，避免 j 出現負數。
🔑 Takeaways#
- Pattern: 二分搜尋分割位置
- 關鍵技巧: 這題的核心觀念是「中位數 = 找到正確的分割線使左右兩半等長且左半部 <= 右半部」。這個分割線的思維方式也可以用在其他「找第 k 大」的問題上