这道题在力扣官网上面是困难难度。但是假如利用好 C++ 的优先队列或者利用好大根堆和小根堆，这道题的思路其实很简单。
题目描述：
题号：295
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
-
例如
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以内的答案将被接受。
解题思路：
思路一：优先队列
初始化两个空堆：一个最大堆（maxHeap）和一个最小堆（minHeap）。
-
将新数字与
maxHeap的堆顶（即较小一半的最大值）进行比较。 -
如果新数字小于等于
maxHeap的堆顶，则将其添加到maxHeap中。此时，我们需要检查两个堆的大小关系，确保maxHeap的大小始终小于等于minHeap的大小，或相差1。如果maxHeap的大小超过了minHeap的大小加1，我们需要将maxHeap的堆顶元素移除，并添加到minHeap中。 -
否则，将新数字的负值添加到
minHeap中。同样，我们需要检查两个堆的大小关系。如果minHeap的大小超过了maxHeap的大小，我们需要将minHeap的堆顶元素（取负后）移除，并添加到maxHeap中。
如果两个堆的大小不一样，则中位数为 maxHeap 的堆顶。
否则，中位数为 maxHeap 堆顶和 minHeap 堆顶的值相加除以 2。
时间复杂度：O(log N)
空间复杂度：O(N)
C++
// C++
class MedianFinder {priority_queue<int> bigHeap; // small part, extra onepriority_queue<int, vector<int>, greater<int>> smallHeap; // big part
public:MedianFinder() {
}void addNum(int num) {if(bigHeap.size() == smallHeap.size()) {smallHeap.push(num);bigHeap.push(smallHeap.top());smallHeap.pop();} else {bigHeap.push(num);smallHeap.push(bigHeap.top());bigHeap.pop();}}double findMedian() {if(bigHeap.size() == smallHeap.size()) {return (bigHeap.top() + smallHeap.top()) / 2.0;}return bigHeap.top();}
};
/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/// go
// 定义一个最大堆
type BigHeap []int func (h BigHeap) Len() int { return len(h) }
func (h BigHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h BigHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *BigHeap) Push(x interface{}) { *h = append(*h, x.(int))
} func (h *BigHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x
} // 定义一个最小堆
type SmallHeap []int func (h SmallHeap) Len() int { return len(h) }
func (h SmallHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h SmallHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *SmallHeap) Push(x interface{}) { *h = append(*h, x.(int))
} func (h *SmallHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x
} type MedianFinder struct { bigHeap BigHeap smallHeap SmallHeap
} func Constructor() MedianFinder { return MedianFinder{ bigHeap: make(BigHeap, 0), smallHeap: make(SmallHeap, 0), }
} func (this *MedianFinder) AddNum(num int) { if len(this.bigHeap) == len(this.smallHeap) { heap.Push(&this.smallHeap, num) heap.Push(&this.bigHeap, heap.Pop(&this.smallHeap).(int)) } else { heap.Push(&this.bigHeap, num) heap.Push(&this.smallHeap, heap.Pop(&this.bigHeap).(int)) }
} func (this *MedianFinder) FindMedian() float64 { if len(this.bigHeap) == len(this.smallHeap) { return float64(this.bigHeap[0]+this.smallHeap[0]) / 2.0 } return float64(this.bigHeap[0])
}
/*** Your MedianFinder object will be instantiated and called as such:* obj := Constructor();* obj.AddNum(num);* param_2 := obj.FindMedian();*/
