📝 题目描述

题目链接：数据流的中位数

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

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

实现 MedianFinder 类:

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

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 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

💡 解题思路

方法一：双堆法

我们只关心处在中间位置的数，两端的数字是否有序其实并不重要。我们可以把数据流切成两半：

  • 较小的一半：存放在一个大顶堆（Max-Heap）中。大顶堆的堆顶是这一半里的最大值（即靠近中位数的那个值）。
  • 较大的一半：存放在一个小顶堆（Min-Heap）中。小顶堆的堆顶是这一半里的最小值（也是靠近中位数的那个值）。

维护规则（核心逻辑）：

  1. 数量平衡：我们要保证两个堆的元素个数差不超过 1。通常我们规定大顶堆可以比小顶堆多 1 个元素，或者两者一样多。
  2. 大小隔离：大顶堆里的所有元素，必须全部小于等于小顶堆里的所有元素。为了保证这一点，每次新来一个数，我们可以先把它扔进大顶堆，然后把大顶堆的堆顶（当前大顶堆的最大值）弹出来，扔进小顶堆（为了防止新来的数字比小顶堆大）。
  3. 如果经过上述操作后，小顶堆的大小超过了大顶堆，我们就把小顶堆的堆顶弹出来，扔回大顶堆。

方法二：多重有序集合 + 双指针

优化解法

🔧 代码实现

1、双堆法

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
class MedianFinder {
private:
    // 大顶堆，存储较小的一半数据
    std::priority_queue<int> maxHeap; 
    // 小顶堆，存储较大的一半数据
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; 

public:
    MedianFinder() {
    }
    
    void addNum(int num) {
        // 1. 先将元素加入大顶堆
        maxHeap.push(num);
        // 2. 将大顶堆的最大值（堆顶）转移到小顶堆，保证大顶堆的所有元素 <= 小顶堆的所有元素
        minHeap.push(maxHeap.top());
        maxHeap.pop();

        // 3. 维护大小平衡：保证 maxHeap 的大小始终等于 minHeap，或者比 minHeap 多 1
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        // 如果元素总数是奇数，大顶堆比小顶堆多一个元素，中位数就是大顶堆的堆顶
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        }
        // 如果元素总数是偶数，中位数是两个堆顶的平均值
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

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

2、多重有序集合 + 双指针

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
class MedianFinder {
public:
    multiset<int> nums;
    multiset<int>::iterator left, right;
    MedianFinder() : left(nums.end()) {
        right = nums.end();
    }
    
    void addNum(int num) {
        const size_t n = nums.size();

        nums.insert(num);
        if (!n){
            // nums为空
            left = right = nums.begin();
        } else if (n & 1) {
            // 判断是否为奇数
            if (num < *left) {
                left--;
            } else {
                right++;
            }
        } else{
            // 如果是偶数
            if (num > *left && num < *right) {
                left++;
                right--;
            } else if (num >= *right) {
                left++;
            } else {
                right--;
                left= right;
            }
        }
    }
    
    double findMedian() {
        return (*left + *right) / 2.0;
    }
};

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

📊 复杂度分析

1、双堆法

  • 时间复杂度：
    • addNum()：O(logn)O(logn)，堆的插入（push）和删除（pop）操作的时间复杂度都是 O(logn)O(logn)。每次添加数字最多涉及几次堆操作，常数极小，效率非常高。
    • findMedian()：O(1)O(1)，直接获取堆顶元素即可。
  • 空间复杂度：O(n)O(n)，两个堆加起来存储了数据流中的所有元素。

2、优化解法

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

🎯 总结

  • 核心思想：将中位数的思路转换为两个堆。