时间轴

2025-12-19

init

题目：

P295 数据流的中位数

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

对顶堆，一个最大堆存前半部分，一个最小堆存后半部分。

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
54
55
56
57
58
59
#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;
                }
        }
};

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