目录
1 队列 - v2.0
2 295. 数据流的中位数
2.1 解题思路
2.2 举例说明
2.3 维持队列
2.4 求中位数
2.5 完整代码
菜鸟做题，语言是 C++
1 队列 - v2.0
排序规则果然和名字是反过来的：
// 大根堆
priority_queue<int, vector<int>, less<int>> queMin;
// 小根堆
priority_queue<int, vector<int>, greater<int>> queMax;2 295. 数据流的中位数
2.1 解题思路
解题思路：
- 维护两个优先队列 queMin 和 queMax
- 前者（是大根堆）存放比中位数 midNum 小的数
- 后者（是小根堆）存放比中位数 midNum 大的数
解题要点：
- 维护 midNum 以进行比较
- 保持 queMin 和 queMax 的大小基本一致
本质上就是将 nums 数组砍半，并且是按从小到大的顺序分别存储在 queMin 和 queMax 中的。到时候，中位数必定出自 queMin 或 queMax 的根元素。
2.2 举例说明
假设 nums 是 [4，5，2，1，3] 。
对于第一个数字 4，我们可以不分青红皂白地把它插入到 queMin 中，同时更新中位数为 4；对于第二个数字 5，由于 5 大于中位数，因此插入 queMax 中，同时更新中位数为 4.5；对于第三个数字 2，由于 2 小于中位数，因此插入 queMin 中。
对于第四个数字 1，由于 1 小于中位数，因此插入 queMin 中。注意：这个时候 queMin 比 queMax 多两个元素了，不满足 “砍半” 要求！因此我们需要将 4 转移到 queMax 中，同时更新中位数为 3。对于第五个数字 3，由于 3 等于中位数，因此随机插入 queMin 中。
2.3 维持队列
对 2.2 节思路的实现
void addNum(int num) {
if (!queMin.size()) {
queMin.push(num);
return;
}
midNum = findMedian();
if (num < midNum) {
if (queMin.size() > queMax.size()) {
queMax.push(queMin.top());
queMin.pop();
}
queMin.push(num);
} else {
if (queMin.size() < queMax.size()) {
queMin.push(queMax.top());
queMax.pop();
}
queMax.push(num);
}
}2.4 求中位数
代码逻辑：
- 若 queMin 和 queMax 不一样长，则中位数是较长一方的根元素
- 若 queMin 和 queMax 一样长，则中位数等于二者根元素之和 / 2
double findMedian() {
double ans;
if (queMin.size() < queMax.size()) {
ans = queMax.top();
} else if (queMin.size() > queMax.size()) {
ans = queMin.top();
} else {
ans = (queMin.top() + queMax.top()) / 2.0;
}
return ans;
}2.5 完整代码
class MedianFinder {
private:
priority_queue<int, vector<int>, less<int>> queMin;
priority_queue<int, vector<int>, greater<int>> queMax;
int midNum;
public:
MedianFinder() { }
void addNum(int num) {
if (!queMin.size()) {
queMin.push(num);
return;
}
midNum = findMedian();
if (num < midNum) {
if (queMin.size() > queMax.size()) {
queMax.push(queMin.top());
queMin.pop();
}
queMin.push(num);
} else {
if (queMin.size() < queMax.size()) {
queMin.push(queMax.top());
queMax.pop();
}
queMax.push(num);
}
}
double findMedian() {
double ans;
if (queMin.size() < queMax.size()) {
ans = queMax.top();
} else if (queMin.size() > queMax.size()) {
ans = queMin.top();
} else {
ans = (queMin.top() + queMax.top()) / 2.0;
}
return ans;
}
};
