力扣 295. 数据流的中位数[堆]

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 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 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

• -105 <= num <= 105
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 5 * 104 次调用 addNum 和 findMedian

题解

PS：如果对堆不了解可以看这里堆介绍与实现

首先来举两个例子，

例1：arr=1,2,3,4,5，那么中位数即中间的3.  例2：arr=1,2,3,4,5,6，那么中位数是3,4之和除以二，在这里我们将3,4分为称为前中位数和后中位数。

也就是说将原数组arr继续划分，分为前有序数组和后有序数组。下面是示例的划分：

eg1:
前有序数组        后有序数组
1   2   3          4   5
则中位数为前有序数组中的最大值3
eg2:
前有序数组        后有序数组
1   2   3         4   5   6
则中位数为 (前有序数组中的最大值3+后有序数组最小值4)/2=3.5

 所以只需要将数组进行划分，然后根据元素是奇数个还是偶数个，选取中位数为前有序最大还是进行求和除2.

而堆就可以很好的维护前有序数组迅速获取最大值、后有序数组迅速获取最小值，且动态维护其结构的需求，所以分别采用最大堆和最小堆存储前、后有序数组。记为queLeft和queRight。

分析完数据结构后，需要人为定义要求来方便求中位数：
queLeft和queRight的大小只能是相等或者queLeft比queRight大一。（即例子中的两种情况）

接下来放入元素，动态划分两个数组：

• 当queLeft为空或者num小于等于queLeft栈顶元素（前有序数组第一个值）时，因为queRight的最小值（即后有序数组中第一个值）肯定大于queLeft栈顶元素，所以num只能往左边插入，即放入queLeft中。
  • 因为queLeft放入了新的元素，此时必须检验queLeft和queRight大小是否满足要求，如果queLeft比queRight多了不止一个数，需要将queLeft的栈顶元素给queRight，相当于划分的线往左移动。
• 否则，num往右插入，放入queRight
  • 检验要求，如果queLeft小于queRight，需要将queRight的栈顶元素给queLeft，相当于划分的线往右移动。

当求中位数时，根据元素是奇数个还是偶数个选取，即queLeft和queRight大小是否相等。

class MedianFinder {
public:
    priority_queue<int,vector<int>,less<int>> queLeft;//前有序数组,小顶堆
    priority_queue<int,vector<int>,greater<int>> queRight;//后有序数组，大顶堆
    MedianFinder() {

    }
    
    void addNum(int num) {
       if(queLeft.empty()||num<=queLeft.top())//刚开始或者应该往左插入
       {
           queLeft.push(num);
           if(queRight.size()+1<queLeft.size())//不能满足满足L最多比R多一个或LR相等
           {
               queRight.push(queLeft.top());
               queLeft.pop();
           }
       }
       else//往右插入
       {
           queRight.push(num);
           if(queRight.size()>queLeft.size())//不能满足满足L最多比R多一个或LR相等
           {
                queLeft.push(queRight.top());
                queRight.pop();
           }
       }
    }
    
    double findMedian() {
       if(queLeft.size()==queRight.size()){
           return (queLeft.top()+queRight.top())/2.0;
       }
       else
            return queLeft.top();
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */