題目描述:設計資料結構,支援動態新增數字並在 O(log n) 時間內查詢當前中位數。
解題思路:雙堆法:用一個最大堆(max-heap)存較小的一半,一個最小堆(min-heap)存較大的一半。維護不變量:兩個堆的大小差不超過 1,且 max-heap 的最大值 <= min-heap 的最小值。新增元素時,先推入 max-heap,再將 max-heap 的最大值移至 min-heap(保持有序),最後若大小不平衡則從 min-heap 還回一個。查詢中位數:若兩堆大小相同取兩頂平均;否則取較大堆的頂端。
時間複雜度:addNum O(log n);findMedian O(1)。
空間複雜度:O(n) — 兩個堆合計儲存所有元素。
addNum(num): 1. Push num to maxHeap 2. Push maxHeap.top() to minHeap, pop from maxHeap 3. If minHeap.size() > maxHeap.size(): push minHeap.top() to maxHeap, pop from minHeap findMedian(): 1. If sizes equal: return (maxHeap.top + minHeap.top) / 2.0 2. Else: return maxHeap.top (larger heap holds median)
排序陣列 O(n) 插入,O(1) 查詢:維護排序陣列,二分插入 — 插入複雜度更差。
多重集 O(log n) 插入,O(n) 中位數:用 BST(樹集),中位數查詢需遍歷 — 中位數複雜度更差。