剑指offer41 数据流中的中位数

发表于 | 分类于 |
字数统计: 582 | 阅读时长 ≈ 2

链接

https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/

题意

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

解法

需要维护一个数据结构，可以动态添加数据并且实时计算中位数
正解也想出来了，构造两个优先队列
一个最大堆一个最小堆
每次维护这两个队列，需要求中位数的时候只需要根据两个队列中数的数量进行判断返回堆顶就可以
我一开始的写法是判断要插入的数和堆顶的大小，但是这样的判断过于繁琐了
其实只需要判断一下两个队列的大小，并且把数插入较多的队列
然后再返回这一队列的顶部，再插入另一个队列就可以满足有序的排列

代码

需要判断大小

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
class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int> q1; // 大顶堆
    priority_queue<int, vector<int>, greater<int>> q2; // 小顶堆
    MedianFinder() {

    }
    
    void addNum(int num) {
        int m = q1.size(), n = q2.size();
        if (m == 0) {
            q1.push(num);
        }
        else if (num < q1.top()) {
            if (m == n) {
                q1.push(num);
            }
            else {
                q2.push(q1.top());
                q1.pop();
                q1.push(num);
            }
        }
        else if (n == 0) {
            q2.push(num);
        }
        else if (num > q2.top()) {
            if (m == n) {
                q1.push(q2.top());
                q2.pop();
                q2.push(num);
            }
            else {
                q2.push(num);
            }
        }
        else {
            if (m == n) {
                q1.push(num);
            }
            else {
                q2.push(num);
            }
        }
    }
    
    double findMedian() {
        int m = q1.size(), n = q2.size();
        // cout << m << ' ' << n << endl;
        if ((m + n) % 2) {
            return q1.top();
        }
        else {
            return (q1.top() + q2.top()) / 2.0;
        }
    }
};

优化后

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
class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int> q1; // 大顶堆
    priority_queue<int, vector<int>, greater<int>> q2; // 小顶堆
    MedianFinder() {

    }
    void addNum(int num) {
        if (q1.size() > q2.size()) {
            q1.push(num);
            q2.push(q1.top());
            q1.pop();       
        }
        else {
            q2.push(num);
            q1.push(q2.top());
            q2.pop();
        }
    }
    
    double findMedian() {
        if (q1.size() != q2.size()) {
            return q1.top();
        }
        else {
            return (q1.top() + q2.top()) / 2.0;
        }
    }
};