【LeetCode热题100】【堆】数据流的中位数
题目链接：295. 数据流的中位数 - 力扣（LeetCode）
不停插入元素要求找到每个状态的中位数，用两个堆，把中位数左边的数记为left，右边的数记为right，一个大顶堆记录小于等于中位数的left，一个小顶堆记录大于中位数的right，数组长度为奇数时大顶堆比小顶堆多一个中位数，数组长度为偶数时，中位数就是两个堆顶的平均值
插入元素时，如果两个堆长度一样，先入小顶堆，这样小顶堆堆顶就是right里面最小的，弹出来放到left里面，此时left比right多一个数，并且left堆顶就是中位数，因为它比right都小，比left都大
如果left堆比right堆多一个数，那么先入left，那么left堆顶是left里面最大的数，弹出来送到right里面去，这样left和right数目相同，并且left堆顶元素小于right，right堆顶元素大于left，两个平均值就是中位数
注意优先队列默认是大顶堆
class MedianFinder {
public:
priority_queue<int> left;
priority_queue<int, vector<int>, greater<int> > right;
MedianFinder() {
}
void addNum(int num) {
if (left.size() == right.size()) {
right.push(num);
left.push(right.top());
right.pop();
} else {
left.push(num);
right.push(left.top());
left.pop();
}
}
double findMedian() {
return left.size() == right.size() ? (left.top() + right.top()) / 2.0 : left.top();
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-04-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
