编程知识 cdmana.com

力扣- 剑指 Offer 41题 数据流中的中位数(C++)- 大顶堆、小顶堆

题目链接:https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
题目如下:
在这里插入图片描述

class MedianFinder {
    
public:
    /** initialize your data structure here. */
    MedianFinder() {
    

    }
    
    void addNum(int num) {
    
        //目的:minheap中放较大的元素,堆顶为最小的元素;maxheap中放较小的元素,堆顶为最大的元素
        //如果是奇数:大顶堆元素数-小顶堆元素数=1
        //如果是偶数:大顶堆元素数=小顶堆元素数
        if(maxheap.size()==0||num<maxheap.top()) maxheap.push(num);
        else minheap.push(num);

        while(maxheap.size()<minheap.size()){
    //小顶堆元素放到大顶堆
            int temp=minheap.top();
            minheap.pop();
            maxheap.push(temp);
        }

        while(minheap.size()<maxheap.size()-1){
    //大顶堆元素放到小顶堆
            int temp=maxheap.top();
            maxheap.pop();
            minheap.push(temp);
        }
    }
    
    double findMedian() {
    
        if(maxheap.size()>minheap.size()) return maxheap.top();
        else return (maxheap.top()+minheap.top())/2.0;
    }
private:
    priority_queue<int> maxheap;//放较小的元素
    priority_queue<int,vector<int>,greater<int>> minheap;//放较大的元素
};

/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */

版权声明
本文为[JIngles123]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_40467670/article/details/126179313

Scroll to Top