【剑指Offer】数据流中的中位数

Posted on | In ,

题目

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

实现

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
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(5, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
});

private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

public void Insert(Integer num) {
    if (maxHeap.size() == minHeap.size())
        maxHeap.add(num);
    else
        minHeap.add(num);

    if (!minHeap.isEmpty() && !maxHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
        maxHeap.offer(minHeap.poll());
        minHeap.offer(maxHeap.poll());
    }
}

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