leetcode 困难 —— 数据流的中位数（优先队列）

题目：
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

题解：
① 双指针 + 有序集合
用一个有序集合存储，然后取其中中间那一个或者中间那两个就行

但有序集合中，不能直接取其中第 n 个大的元素
每一次遍历到第 n 个，又会导致效率过低
所以通过双指针，指向中间那一个或者中间那两个

然后根据插入值的大小和指针指向的值的大小比对，判断不同情况，进行移动指针

（这个有序集合不能是 set，因为 set 会去重，可以用 multiset）

② 优先队列
（最开始不知道 multiset，所以用的这个方法）

既然想不到用什么集合能快速找到第 n 个大小的值
但应该能想到我们可以快速会得到最大值和最小值，优先队列

一个序列我们可以分为
左边 n 个数              中位数              右边 n 个数

左边维护一个优先队列，我们只需要知道最大值
右边维护一个优先队列，我们只需要知道最小值

然后根据不同情况，进行不同的插入优先队列，取出值的操作即可

代码如下：

class MedianFinder {
public:bool flag = true;int left = INT_MAX, right = INT_MAX;priority_queue<int> left_temp;priority_queue<int, vector<int>, greater<int> > right_temp;MedianFinder() {}void addNum(int num) {if(left == INT_MAX) {left = right = num;flag = !flag;return;}if(num >= right) {if(flag) {left_temp.push(left);right_temp.push(num);left = right;}else {right_temp.push(num);right = right_temp.top();right_temp.pop();}}else if(num <= left) {if(flag) {left_temp.push(num);right_temp.push(right);right = left;}else {left_temp.push(num);left = left_temp.top();left_temp.pop();}}else {left_temp.push(left);right_temp.push(right);left = right = num;}flag = !flag;}double findMedian() {return (left + right) / 2.0;}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/