🌗 剑指 Offer 41. 数据流中的中位数

难度: 🌗

问题描述

---

解法

class MedianFinder {
    // 思路：
    // 维护 2 个优先队列
    PriorityQueue<Integer> one;
    PriorityQueue<Integer> two;

    /** initialize your data structure here. */
    public MedianFinder() {
        one = new PriorityQueue<>((a, b) -> {
            return b - a; // 大根堆
        });
        two = new PriorityQueue<>(); 
    }
    
    public void addNum(int num) {
        int l1 = one.size(); // l1 始终 >= l2
        int l2 = two.size();
        if(l1 == 0) {
            one.offer(num);
            return;
        }
        if(l1 == l2) {
            // 最终需要保证 l1 > l2
            int p2 = two.peek();
            if(num > p2) {
                two.poll();
                two.offer(num);
                one.offer(p2);
            } else {
                one.offer(num);
            }
        } else {
            // 最终保证 l1 == l2
            int p1 = one.peek();
            if(num < p1) {
                one.poll();
                one.offer(num);
                two.offer(p1);
            } else {
                two.offer(num);
            }
        }
    }
    
    public double findMedian() {
        int l1 = one.size();
        int l2 = two.size();
        if(l1 == l2) {
            double res = one.peek();
            res += two.peek();
            res /= 2;
            return res;
        } else {
            return one.peek();
        }
    }
}

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

---

输出