295. 数据流的中位数

📝 题目描述

中位数是有序列表中间的数：

• 若列表长度为奇数，中位数是中间那个数；
• 若列表长度为偶数，中位数是中间两个数的平均值。

要求实现 MedianFinder 类，支持两个操作：

1. MedianFinder()：初始化对象；
2. void addNum(int num)：将数字 num 加入数据流；
3. double findMedian()：返回当前数据流的中位数（误差在 (10^{-5}) 内即可）。

---

📌 示例

示例 1

输入：

["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]

输出：

[null, null, null, 1.5, null, 2.0]

解释：

• MedianFinder medianFinder = new MedianFinder();
• medianFinder.addNum(1) → 数据流：[1]
• medianFinder.addNum(2) → 数据流：[1,2]
• findMedian() → 中位数是 ((1+2)/2 = 1.5)
• medianFinder.addNum(3) → 数据流：[1,2,3]
• findMedian() → 中位数是 2.0

---

🚀 最优解：双堆法（大顶堆+小顶堆）

🔍 思路解析

核心策略：用两个堆拆分数据流，让中位数始终处于堆顶位置，实现高效的插入和查询：

1. 维护两个堆：
   • 大顶堆 A：存储数据流中较小的一半元素，堆顶是这一半的最大值；
   • 小顶堆 B：存储数据流中较大的一半元素，堆顶是这一半的最小值；
2. 保持堆的平衡规则：
   • A 的大小 要么等于 B 的大小，要么 比 B 大 1（保证奇数长度时，A 的堆顶就是中位数）；
3. 添加元素 num 的逻辑：
   • 若 A、B 大小相等：先把 num 加入 B，再把 B 的堆顶移到 A（让 A 多一个元素）；
   • 若 A 比 B 大：先把 num 加入 A，再把 A 的堆顶移到 B（让两者大小平衡）；
4. 查询中位数的逻辑：
   • 若 A、B 大小相等：中位数 = (A堆顶 + B堆顶) / 2.0；
   • 若 A 比 B 大：中位数 = A堆顶。

---

✅ 完整代码（Java）

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 创建MedianFinder对象
        MedianFinder medianFinder = new MedianFinder();

        // 读取操作数量
        int m = scanner.nextInt();
        scanner.nextLine(); // 消费换行符

        // 处理每个操作
        for (int i = 0; i < m; i++) {
            String operation = scanner.nextLine();
            String[] parts = operation.split(" ");

            if (parts[0].equals("addNum")) {
                int num = Integer.parseInt(parts[1]);
                medianFinder.addNum(num);
            } else if (parts[0].equals("findMedian")) {
                double median = medianFinder.findMedian();
                // 输出结果，如果是整数则输出整数形式，否则输出小数形式
                if (median == (int) median) {
                    System.out.println((int) median);
                } else {
                    System.out.println(median);
                }
            }
        }

        scanner.close();
    }
}

class MedianFinder {
    // A：大顶堆（存较小的一半元素）；B：小顶堆（存较大的一半元素）
    PriorityQueue<Integer> A, B;

    public MedianFinder() {
        // Java默认是小顶堆，用Comparator实现大顶堆
        A = new PriorityQueue<>((x, y) -> (y - x));
        B = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (A.size() == B.size()) {
            B.add(num);
            A.add(B.poll());
        } else {
            A.add(num);
            B.add(A.poll());
        }
    }

    public double findMedian() {
        if (A.size() != B.size()) {
            // 奇数长度，A的堆顶是中位数
            return A.peek();
        } else {
            // 偶数长度，取两个堆顶的平均值
            return (A.peek() + B.peek()) / 2.0;
        }
    }
}

---

🧠 通俗易懂解释

可以把数据流想象成“分成左右两堆”：

• 左堆（A，大顶堆）：装较小的数，堆顶是左堆最大的数；
• 右堆（B，小顶堆）：装较大的数，堆顶是右堆最小的数；
• 我们保证左堆最多比右堆多1个数，这样中位数要么是左堆顶（奇数个元素），要么是左右堆顶的平均数（偶数个元素）。

以示例1的添加过程为例：

1. 加 1：A、B都为空 → 先加B（B=[1]），再移B顶到A → A=[1]，B=[]；
2. 加 2：A比B大 → 先加A（A=[2,1]），再移A顶到B → A=[1]，B=[2]；
3. 查中位数：A、B大小相等 → (1+2)/2=1.5；
4. 加 3：A、B相等 → 先加B（B=[3,2]），再移B顶到A → A=[2,1]，B=[3]；
5. 查中位数：A比B大 → A顶是2.0。

---

⏱ 时间复杂度

• addNum：(O(\log n)) 优先队列的插入/弹出操作时间复杂度为对数级，每次add最多执行2次堆操作；
• findMedian：(O(1)) 直接取堆顶元素，无需额外计算。

---

💾 空间复杂度

(O(n))

需要存储数据流中的所有元素，空间消耗与元素数量成正比。

大顶堆  小顶堆 
1234    456