LeetCode 热题 100 | 堆（三）

目录

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;
    }
};