Median

题目描述[原题链接][https://www.acwing.com/problem/content/description/88/]

如何得到一个数据流中的中位数？

如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。

如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

样例

输入：1, 2, 3, 4

输出：1,1.5,2,2.5

解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。

算法描述

定义一个大根堆和一个小根堆，每次向大根堆中添加元素，添加完成后，判断两个堆顶的元素大小，如果大根堆堆顶的元素大于小根堆的堆顶，交换元素，如果大根堆元素个-小根堆元素大于1，大根堆弹出一个元素加入到小根堆中，直到最后结束。

C++代码

class Solution {
public:
    
    priority_queue<int> maxQue;
    priority_queue<int,vector<int>,greater<int>> minQue;
    
    void insert(int num){
        maxQue.push(num);
        if(minQue.size()&&minQue.top()<maxQue.top()){
            int maxv=maxQue.top();
            int minv=minQue.top();
            maxQue.pop();
            minQue.pop();
            maxQue.push(minv);
            minQue.push(maxv);
        }
        
        if(maxQue.size()-minQue.size()>1){
            minQue.push(maxQue.top());
            maxQue.pop();
        }
        
    }

    double getMedian(){
        if((maxQue.size()+minQue.size())&1)return maxQue.top();
        return (maxQue.top()+minQue.top())/2.0;
    }
};

Java代码

class Solution {
    
    Comparator<Integer> cmp = new Comparator<Integer>(){
        public int compare(Integer e1,Integer e2){
            return e2-e1;
        }
    };
    PriorityQueue<Integer> minQue = new PriorityQueue<>();
    PriorityQueue<Integer> maxQue = new PriorityQueue<>(cmp);

    public void insert(Integer num) {
        maxQue.add(num);
        if(!minQue.isEmpty()&&maxQue.peek()>minQue.peek()){
            int maxV = maxQue.poll();
            int minV = minQue.poll();
            maxQue.add(minV);
            minQue.add(maxV);
        }
        if(maxQue.size()-minQue.size()>1){
            minQue.add(maxQue.poll());
        }
    }

    public Double getMedian() {
        if((maxQue.size()+minQue.size())%2==1)return maxQue.peek()*1.0;
        return (maxQue.peek()+minQue.peek())/2.0;
    }

}