問題描述
中位數是有序整數列表中的中間值。如果列表的大小是偶數，則沒有中間值，中位數是兩個中間值的平均值。
- 例如?
arr = [2,3,4]?的中位數是?3?。 - 例如?
arr = [2,3]?的中位數是?(2 + 3) / 2 = 2.5?。
實現 MedianFinder 類:
-
MedianFinder()初始化?MedianFinder?對象。 -
void addNum(int num)?將數據流中的整數?num?添加到數據結構中。 -
double findMedian()?返回到目前為止所有元素的中位數。與實際答案相差?10-5?以內的答案將被接受。
解題思路
為什么使用兩個堆？
在面對數據流時，我們往往需要實時添加元素并頻繁查詢中位數。使用數組或列表雖然簡單，但每次添加元素后要求的排序操作是低效的。為了優化這一過程，可以采用兩個堆來分別維護數據的較小部分和較大部分：
- 最大堆用來存儲當前元素的較小一半，堆頂是這部分元素的最大值。
- 最小堆存儲較大一半的元素，其堆頂是這部分元素的最小值。
這種結構使得我們可以在對數時間內調整堆并找到中位數，非常適合處理大規模數據。
代碼實現
class MedianFinder {
private:// 最大堆存儲較小一半元素std::priority_queue<int, std::vector<int>, std::less<int>> maxHeap;// 最小堆存儲較大一半元素std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;public:MedianFinder() {}void addNum(int num) {// 先添加到最大堆maxHeap.push(num);// 保持兩個堆的平衡// 將最大堆的最大值轉移到最小堆minHeap.push(maxHeap.top());maxHeap.pop();// 如果最小堆元素多于最大堆，調整以保持平衡if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();}}double findMedian() {// 如果兩個堆大小相等，取平均if (maxHeap.size() == minHeap.size()) {return (maxHeap.top() + minHeap.top()) / 2.0;} else {// 如果大小不等，最大堆的頂部元素即為中位數return maxHeap.top();}}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/
