自己做的网站如如统计访问量,优秀高端网站建设服务商,wordpress写代码插件,佛山做优化的网络公司目录
1 队列 - v2.0
2 295. 数据流的中位数
2.1 解题思路
2.2 举例说明
2.3 维持队列
2.4 求中位数
2.5 完整代码 菜鸟做题#xff0c;语言是 C 1 队列 - v2.0
排序规则果然和名字是反过来的#xff1a;
// 大根堆
priority_queueint, vectorint语言是 C 1 队列 - v2.0
排序规则果然和名字是反过来的
// 大根堆
priority_queueint, vectorint, lessint queMin;
// 小根堆
priority_queueint, vectorint, greaterint queMax; 2 295. 数据流的中位数
2.1 解题思路
解题思路
维护两个优先队列 queMin 和 queMax前者是大根堆存放比中位数 midNum 小的数后者是小根堆存放比中位数 midNum 大的数
解题要点
维护 midNum 以进行比较保持 queMin 和 queMax 的大小基本一致 本质上就是将 nums 数组砍半并且是按从小到大的顺序分别存储在 queMin 和 queMax 中的。到时候中位数必定出自 queMin 或 queMax 的根元素。 2.2 举例说明
假设 nums 是 [45213] 。
对于第一个数字 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_queueint, vectorint, lessint queMin;priority_queueint, vectorint, greaterint 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;}
};
