Poison

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
35
class MedianFinder {

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

    public MedianFinder() {
        // --------
        //  \    /
        //   \ /
        //   / \
        //  /   \
        // --------
        this.minHeap = new PriorityQueue<>(); // 最小堆，倒置，同时承载奇数时多的那一个元素
        this.maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); // 最大堆
    }

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

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

}
Reference

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