【Hot 100】295. 数据流的中位数

• 🙋‍♂️ 作者：海码007
• 📜 专栏：算法专栏
• 💥 标题：【Hot 100】295. 数据流的中位数
• ❣️ 寄语：书到用时方恨少，事非经过不知难！

引言

中位数的题目，在吉比特面试的时候遇到过，大量的数据如何快速查找中位数，而且还有频繁的插入和删除操作。

数据流的中位数

• 🎈 题目链接：
• 🎈 做题状态：

我的解题

class MedianFinder {
private:priority_queue<int, vector<int>, less<int>> queMin;priority_queue<int, vector<int>, greater<int>> queMax;public:MedianFinder() {}void addNum(int num) {if (queMin.empty() || num <= queMin.top()){// 如果queMin为空，或者当前数值小于queMin，则将数据插入到queMin中queMin.push(num);// 插入完数据后，还需要平衡两边的队列大小if (queMax.size() + 1 < queMin.size()){// 两边相差2个数据时，需要将多的转移到少的容器中queMax.push(queMin.top());queMin.pop();}} else{// 当前数据大于 queMin 中的最大值，需插入 queMax 中queMax.push(num);// 插入之后需要平衡，因为 queMin 的设定是大于等于 queMax 中元素个数if (queMax.size() > queMin.size()){queMin.push(queMax.top());queMax.pop();}}}double findMedian() {// 如果 queMin 个数大于 queMax，则中位数就是 queMin 的topif (queMin.size() > queMax.size()) return queMin.top();return (queMax.top() + queMin.top()) / 2.0;}
};