数据流中的中位数 Find Median from Data Stream

佚名 6年前 (2019-04-17) 随笔 1740人围观抢沙发百度已收录

2019-04-17 16:34:50

问题描述：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

问题求解：

class MedianFinder {
    PriorityQueue<Integer> smaller;
    PriorityQueue<Integer> larger;

    /** initialize your data structure here. */
    public MedianFinder() {
        smaller = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        larger = new PriorityQueue();
    }

    public void addNum(int num) {
        if (smaller.isEmpty()) smaller.add(num);
        else if (num < smaller.peek()) {
            smaller.add(num);
            if (smaller.size() - 2 == larger.size()) 
                larger.add(smaller.poll());
        }
        else {
            larger.add(num);
            if (larger.size() > smaller.size()) {
                smaller.add(larger.poll());
            }
        }
    }

    public double findMedian() {
        int n = smaller.size() + larger.size();
        if (n % 2 == 0) return (smaller.peek() + larger.peek()) * 0.5;
        else return smaller.peek() * 1.0;
    }   
}