时间轴

2025-12-19

init

题目：

P295 数据流的中位数

https://leetcode.cn/problems/find-median-from-data-stream/description/

用两个优先队列maxHeap和minHeap分别记录小于中位数的数和大于等于中位数的数。

  • 小顶堆，存大的那一半（那么堆顶元素就是大半里面最小的那个，即最接近中心的）
  • 大顶堆，存小的那一半（那么堆顶元素就是小半里面最大的那个，即最接近中心的）

当累计添加的数的数量为奇数时，minHeap中的数的数量比maxHeap多一个，此时中位数为minHeap的队头。当累计添加的数的数量为偶数时，两个优先队列中的数的数量相同，此时中位数为它们的队头的平均值。特别地，当累计添加的数的数量为0时，我们将num添加到minHeap中。

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
48
49
50
#include <vector>
#include <queue>
using std::priority_queue;
using std::vector;

class MedianFinder {
    private:
        priority_queue<int, vector<int>, std::less<int> > max_heap;
        priority_queue<int, vector<int>, std::greater<int> > min_heap;

    public:
        MedianFinder()
        {
        }

        void addNum(int num)
        {
                if (max_heap.empty()) {
                        max_heap.push(num);
                        return;
                }
                if ((max_heap.size() + min_heap.size()) & 0x1) { // 奇数
                        int curr_median = max_heap.top();
                        if (num >= curr_median) {
                                min_heap.push(num);
                        } else {
                                max_heap.pop();
                                min_heap.push(curr_median);
                                max_heap.push(num);
                        }
                } else { // 偶数
                        if (num <= min_heap.top()) {
                                max_heap.push(num);
                        } else {
                                max_heap.push(min_heap.top());
                                min_heap.pop();
                                min_heap.push(num);
                        }
                }
        }

        double findMedian()
        {
                if ((max_heap.size() + min_heap.size()) & 0x1) { // 奇数
                        return (double)max_heap.top();
                } else { // 偶数
                        return ((double)max_heap.top() + (double)min_heap.top()) / 2;
                }
        }
};

leetcode hot 100 rewrite:

对顶堆：

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
48
49
50
51
52
53
#include <queue>
#include <vector>

using std::priority_queue;
using std::vector;

class MedianFinder {
    private:
        priority_queue<int, vector<int>, std::less<int> > max_heap; // 存小的那一部分
        priority_queue<int, vector<int>, std::greater<int> > min_heap; // 存大的那一部分

    public:
        MedianFinder()
        {
        }

        void addNum(int num)
        {
                if (max_heap.empty()) {
                        max_heap.push(num);
                        return;
                }

                if ((max_heap.size() + min_heap.size()) % 2 != 0) { // 奇数
                        int curr_mid = max_heap.top();
                        if (num >= curr_mid) {
                                min_heap.push(num);
                        } else {
                                min_heap.push(curr_mid);
                                max_heap.pop();
                                max_heap.push(num);
                        }

                } else { //偶数
                        if (num <= min_heap.top()) {
                                max_heap.push(num);
                        } else {
                                max_heap.push(min_heap.top());
                                min_heap.pop();
                                min_heap.push(num);
                        }
                }
        }

        double findMedian()
        {
                if ((max_heap.size() + min_heap.size()) % 2 != 0) { // 奇数
                        return max_heap.top();
                } else {
                        return (max_heap.top() + min_heap.top()) / 2.0;
                }
        }
};