Description
設計一個資料結構，支援從資料流中新增整數，並能隨時找到目前所有已加入整數的中位數。若元素個數為偶數，中位數為中間兩數的平均值。
Example:
Input: [“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”] [[], [1], [2], [], [3], []] Output: [null, null, null, 1.5, null, 2.0]
Intuition#
核心思路：用兩個 Heap（Max Heap 存較小半邊，Min Heap 存較大半邊），中位數就在兩個堆頂之間。
- 中位數把資料分成「較小的一半」和「較大的一半」
- Max Heap（左半邊）的堆頂是較小一半的最大值
- Min Heap（右半邊）的堆頂是較大一半的最小值
- 維持兩個 Heap 大小差不超過 1，中位數就在堆頂
Approaches#
1: Sorted List（插入排序）#
- 概念: 維護一個有序列表，每次用二分搜尋找到插入位置，中位數直接取中間元素
- 時間複雜度:
O(n)addNum（插入需要移動元素），O(1)findMedian - 空間複雜度:
O(n)
class MedianFinder() {
private val sorted = mutableListOf<Int>()
fun addNum(num: Int) {
var pos = sorted.binarySearch(num)
if (pos < 0) pos = -(pos + 1)
sorted.add(pos, num)
}
fun findMedian(): Double {
val n = sorted.size
return if (n % 2 == 1) {
sorted[n / 2].toDouble()
} else {
(sorted[n / 2 - 1] + sorted[n / 2]) / 2.0
}
}
}⭐2: Two Heaps#
- 概念: Max Heap 存較小半邊，Min Heap 存較大半邊。新數先加入 Max Heap，再平衡兩邊大小。中位數從堆頂取得
- 時間複雜度:
O(log n)addNum，O(1)findMedian - 空間複雜度:
O(n)
class MedianFinder() {
private val small = PriorityQueue<Int>(compareByDescending { it }) // Max Heap (左半邊)
private val large = PriorityQueue<Int>() // Min Heap (右半邊)
fun addNum(num: Int) {
small.offer(num)
// 確保 small 的最大值 <= large 的最小值
if (large.isNotEmpty() && small.peek() > large.peek()) {
large.offer(small.poll())
}
// 平衡大小：small 最多比 large 多 1 個
if (small.size > large.size + 1) {
large.offer(small.poll())
} else if (large.size > small.size) {
small.offer(large.poll())
}
}
fun findMedian(): Double {
return if (small.size > large.size) {
small.peek().toDouble()
} else {
(small.peek() + large.peek()) / 2.0
}
}
}平衡邏輯的順序很重要：先確保值的正確性（小堆的最大 <= 大堆的最小），再平衡大小。順序反過來可能導致錯誤。
🔑 Takeaways#
- Pattern: Two Heaps 是維護動態中位數的經典模式，也適用於滑動視窗中位數等變體
- 關鍵技巧: Max Heap + Min Heap 的組合，讓「較小半邊的最大值」和「較大半邊的最小值」都能 O(1) 取得