📃 题目描述

题目链接：剑指 Offer 41. 数据流中的中位数 (opens new window)

🔔 解题思路

我们用两个优先队列分别记录大于中位数的数（leftHeap，小根堆）和小于等于中位数的数（rightHeap，大根堆）

• 当累计添加的数的数量为奇数时，leftHeap 中的数的数量比 rightHeap 多一个，此时中位数为 leftHeap 的队头
• 当累计添加的数的数量为偶数时，两个优先队列中的数的数量相同，此时中位数为它们的队头的平均值。

当我们尝试添加一个数num 到数据结构中，我们需要分情况讨论：

• num < leftHeap.peek()：此时num 小于等于中位数，我们需要将该数添加到 leftHeap
• num > rightHeap.peek()：此时 num 大于中位数，我们需要将该数添加到 rightHeap 中

特别地，当累计添加的数的数量为 0 时，我们将 num 添加到 leftHeap 中

class MedianFinder {

    // 存储比中位数小的数(大根堆)
    private PriorityQueue<Integer> leftHeap;
    // 存储比中位数大的数(小根堆)
    private PriorityQueue<Integer> rightHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        leftHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        rightHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // 新加入的数在中位数左边
        if (leftHeap.isEmpty() || num <= leftHeap.peek()) {
            leftHeap.offer(num);
            // 保证 leftHeap 数量 >= rightHeap 数量 + 1
            if (leftHeap.size() > rightHeap.size() + 1) {
                rightHeap.offer(leftHeap.poll());
            }
        }
        // 新加入的数在中位数右边
        else {
            rightHeap.offer(num);
            // 保证 leftHeap 数量 >= rightHeap 数量 + 1
            if (rightHeap.size() > leftHeap.size()) {
                leftHeap.offer(rightHeap.poll());
            }
        }
    }
    
    public double findMedian() {
        int count = leftHeap.size() + rightHeap.size();
        if (count % 2 == 0) {
            return (leftHeap.peek() + rightHeap.peek()) / 2.0;
        }

        return leftHeap.peek();
    }
}

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

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：