数据流的中位数

题解思路

方法：双堆法（大顶堆 + 小顶堆）

为了高效地求解中位数，我们可以使用两个堆维护数据流的左右两半部分：

• 最大堆（left，存较小的一半）：堆顶是左半边最大值；
• 最小堆（right，存较大的一半）：堆顶是右半边最小值；

平衡策略：

• 添加元素时，先放入最大堆，再将最大堆堆顶移动到最小堆；
• 如果最小堆元素比最大堆多，则从最小堆弹出一个最小元素到最大堆，确保平衡。

查找中位数：

• 若总数是奇数，中位数为最大堆堆顶；
• 若总数是偶数，中位数为两个堆顶平均值。

复杂度分析

• addNum 时间复杂度：$O(\log n)$（堆操作）
• findMedian 时间复杂度：$O(1)$
• 空间复杂度：$O(n)$

Python 实现

import sys
import heapq

class MedianFinder:
    def __init__(self):
        self.left = []   # 最大堆（存负数）
        self.right = []  # 最小堆

    def addNum(self, num):
        heapq.heappush(self.left, -num)  # 先放到最大堆
        heapq.heappush(self.right, -heapq.heappop(self.left))  # 保证最小堆最小
        if len(self.right) > len(self.left):  # 平衡两个堆
            heapq.heappush(self.left, -heapq.heappop(self.right))

    def findMedian(self):
        if len(self.left) > len(self.right):
            return -self.left[0]
        else:
            return (-self.left[0] + self.right[0]) / 2

# 主程序（ACM风格）
mf = MedianFinder()
q = int(sys.stdin.readline().strip())
for _ in range(q):
    parts = sys.stdin.readline().strip().split()
    if parts[0] == 'add':
        mf.addNum(int(parts[1]))
    elif parts[0] == 'median':
        print(f"{mf.findMedian():.1f}")

C++ 实现

#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;

class MedianFinder {
    priority_queue<int> left; // 大顶堆
    priority_queue<int, vector<int>, greater<int>> right; // 小顶堆

public:
    void addNum(int num) {
        left.push(num);
        right.push(left.top());
        left.pop();

        if (right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }

    double findMedian() {
        if (left.size() > right.size()) return left.top();
        return (left.top() + right.top()) / 2.0;
    }
};

int main() {
    int q;
    cin >> q;
    MedianFinder mf;

    while (q--) {
        string op;
        cin >> op;
        if (op == "add") {
            int x;
            cin >> x;
            mf.addNum(x);
        } else if (op == "median") {
            cout << fixed << setprecision(1) << mf.findMedian() << endl;
        }
    }
    return 0;
}

Java 实现

import java.util.*;

public class Main {
    static class MedianFinder {
        PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> right = new PriorityQueue<>();

        public void addNum(int num) {
            left.offer(num);
            right.offer(left.poll());
            if (right.size() > left.size()) {
                left.offer(right.poll());
            }
        }

        public double findMedian() {
            if (left.size() > right.size()) return left.peek();
            return (left.peek() + right.peek()) / 2.0;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        MedianFinder mf = new MedianFinder();
        while (q-- > 0) {
            String cmd = sc.next();
            if (cmd.equals("add")) {
                int x = sc.nextInt();
                mf.addNum(x);
            } else if (cmd.equals("median")) {
                System.out.printf("%.1f\n", mf.findMedian());
            }
        }
    }
}

Leetcode 76.数据流的中位数-原题链接

题目内容

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 $arr = [2,3,4]$ 的中位数是 $3$ 。
• 例如 $arr = [2,3]$ 的中位数是 $(2 + 3) / 2 = 2.5$ 。

实现 $MedianFinder$ 类:

• $MedianFinder()$初始化 $MedianFinder$对象。
• $void\ addNum(int\ num)$ 将数据流中的整数 $num$添加到数据结构中。
• $double\ findMedian()$ 返回到目前为止所有元素的中位数。与实际答案相差 $10^{-5}$以内的答案将被接受。

输入描述

• 第一行输入一个整数 q，表示操作次数。
• 接下来 q 行，每行是一个操作：
  • 若为 "add x"，表示添加一个数字 x；
  • 若为 "median"，表示查询当前所有数字的中位数。

输出描述

对于每个 "median" 操作，输出一行中位数，保留 1 位小数。

样例1

输入

5
add 1
add 2
median
add 3
median

输出

1.5
2.0

说明

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示：

• $-10^5 <= num <= 10^5$
• 在调用 $findMedian$之前，数据结构中至少有一个元素
• 最多 $5 * 10^4$ 次调用 $addNum$和 $findMedian$