JZ63 数据流中的中位数

本文最后更新于：2022年4月9日 中午

image-20211010155606337

Solution

  • 建立两个堆
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
class Solution {
public:
    priority_queue<int, vector<int>, less<int>> A;    // 大根堆
    priority_queue<int, vector<int>, greater<int>> B;    // 小根堆
    
    void Insert(int num) {
        if (A.size() == B.size()) {
            B.push(num);
            A.push(B.top());
            B.pop();
        } else {
            A.push(num);
            B.push(A.top());
            A.pop();
        }
    }

    double GetMedian() { 
        if (A.size() == B.size()) {
            return (A.top() + B.top()) * 0.5;
        }
        return A.top();
    }

};
  • 使用插排
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> record;
    
    // 插入排序
    void Insert(int num) {
        if (record.empty()) {
            record.push_back(num);
        } else {
            auto it = lower_bound(record.begin(), record.end(), num);
            record.insert(it, num);
        }
    }

    double GetMedian() { 
        int n = record.size();
        if (n & 1)
            return record[n / 2];
        else
            return (record[n /2 -1] + record[n/2])*0.5;
    }
};