ChunNote
0%

leetCode-295:Find Median from Data Stream

发表于 分类于

问题描述

要求实现一个类，类中有两个功能，一个是往类中添加整数，另一个是求已添加的整数列表中的中位数。题目链接：点我

样例输入输出

输入：

[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]

输出：[null, null, null, 1.5, null, 2.0]

解释：

1
2
3
4
5
6
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

输入：

[“MedianFinder”, “addNum”, “findMedian”]
[[], [1], []]

输出：[null, null, 1.0]

解释：

1
2
3
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.findMedian(); // return 1.0

问题解法

维护两个优先队列（大小堆），大堆堆顶元素和小堆堆顶元素对应着中位数，大堆的元素始终不大于小堆中的元素。如果数列总数是奇数，则返回大堆的堆顶元素，如果队列总数是偶数，是取大堆和小堆的堆顶元素的平均值。在处理 addNum 时，先判断当前已有的元素个数，如果当前是奇数的，那新增的值会让小堆元素加一，如果此时大堆堆顶元素比当前元素大，则需要从大堆中取出堆顶元素放如小堆中，然后将当前元素放如大堆中，否则，直接将当前元素放如小堆中。反之亦然。

代码如下

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class MedianFinder {
    private Queue<Integer> oddQueue = new PriorityQueue<>(Comparator.reverseOrder());

    private Queue<Integer> evenQueue = new PriorityQueue<>();

    private boolean isOddNow = false;

    public MedianFinder() {
        oddQueue.clear();
        evenQueue.clear();
        isOddNow = false;
    }

    public void addNum(int num) {
        Integer oddNum = oddQueue.peek();
        Integer evenNum = evenQueue.peek();
        if (isOddNow) {
            if (oddNum > num) {
                oddQueue.poll();
                oddQueue.offer(num);
                evenQueue.offer(oddNum);
            } else {
                evenQueue.offer(num);
            }
            isOddNow = false;
        } else {
            if (evenNum != null && evenNum < num) {
                evenQueue.poll();
                evenQueue.offer(num);
                oddQueue.offer(evenNum);
            } else {
                oddQueue.offer(num);
            }
            isOddNow = true;
        }
    }

    public double findMedian() {
        if (isOddNow) {
            return oddQueue.peek();
        }

        return (oddQueue.peek() + evenQueue.peek()) / 2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */