力扣 295. 数据流的中位数

🔗 https://leetcode.cn/problems/find-median-from-data-stream/

题目

• 数据流中不断有数添加进来，add 表示添加数据，find 返回数据流中的中位数

思路

• 大根堆存储数据流中偏小的数据
• 小根堆存储数据流中偏大的数据
• 若当前的 num 比大根堆的 top 小，则加入到大根堆，反义加入小根堆
• 保证大根堆和小根堆的 size 相差小于等于 1，超过时，挪动一下数据
• 中位数则是 size 大的那个堆的 top，若相等则取 top / 2

代码

class MedianFinder {
public:MedianFinder() {size = 0;}void addNum(int num) {size++;if (maxheap.empty()) {maxheap.push(num);return;}if (num <= maxheap.top()) {maxheap.push(num);} else {minheap.push(num);}if (maxheap.size() - minheap.size() == 2) {minheap.push(maxheap.top());maxheap.pop();}if (minheap.size() - maxheap.size() == 2) {maxheap.push(minheap.top());minheap.pop();}}double findMedian() {if (maxheap.size() > minheap.size()) {return maxheap.top();}if (minheap.size() > maxheap.size()) {return minheap.top();} return ((double)maxheap.top() + minheap.top()) / 2;}std::priority_queue<int, std::vector<int>> maxheap;std::priority_queue<int, std::vector<int>, std::greater<int>> minheap;int size;};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/