295. Find Median from Data Stream 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MedianFinder {

    private final Queue<Integer> minHeap;
    private final Queue<Integer> maxHeap;

    public MedianFinder() {
        //    4
        //  5  6
        this.minHeap = new PriorityQueue<>();

        //    3
        //  1   2
        this.maxHeap = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1)); // 不要忘记设置比较器
    }

    public void addNum(int num) {
        if (maxHeap.size() == minHeap.size()) {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        } else {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }

}

References

295. Find Median from Data Stream
剑指 Offer 41. 数据流中的中位数
面试题 17.20. 连续中值