295. 数据流的中位数【练习C++ STL】

落日映苍穹つ 2022-09-08 14:59 130阅读 0赞

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

\[2,3,4\] 的中位数是 3

\[2,3\] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。  
double findMedian() - 返回目前所有元素的中位数。  
示例：

addNum(1)  
addNum(2)  
findMedian() -> 1.5  
addNum(3)   
findMedian() -> 2  
进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？  
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

使用两个大小顶堆维护，十分方便

class MedianFinder {
    public:
        priority_queue<int,vector<int>,less<int>> left_q;
        priority_queue<int,vector<int>,greater<int>> right_q;
        /** initialize your data structure here. */
        MedianFinder() {
        }
        
        void addNum(int num) {
            if(left_q.empty()||left_q.top()>num)
            {
                left_q.push(num);
                if(left_q.size()-right_q.size()>1)
                {
                    right_q.push(left_q.top());
                    left_q.pop();
                }
            }
            else
            {
                right_q.push(num);
                if(right_q.size()-left_q.size()>1)
                {
                    left_q.push(right_q.top());
                    right_q.pop();
                }
            }
        }
        
        double findMedian() {
            if(left_q.size()>right_q.size())
            {
                return left_q.top();
            }
            if(left_q.size()<right_q.size())
            {
                return right_q.top();
            }
            return 1.0*(right_q.top()+left_q.top())/2;
        }
    };
    
    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder* obj = new MedianFinder();
     * obj->addNum(num);
     * double param_2 = obj->findMedian();
     */