LeetCode刷题实战295：数据流的中位数-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 数据流的中位数，我们先来看题面：

https://leetcode-cn.com/problems/find-median-from-data-stream/

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

示例

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

解题

https://www.cnblogs.com/paulprayer/p/9884332.html

堆是一个非常重要的数据结构，LeetCode网站把这一道划分在“堆”一类中，也是提醒我们使用堆结构。这道题很巧妙，我是听了算法课（牛客网的左程云大牛）的讲解才弄明白。这里的代码是自己听懂了思路，独立写出来的。

关键思路：建立两个堆（使用priority_queue实现），一个大根堆，一个小根堆。

一个大根堆，保存所有整数中较小的1/2;一个小根堆，保存所有整数中较大的1/2；

并且，依次添加元素过程中，两个堆元素个数的差的绝对值不能超过1；这样，两个堆建立好了以后，

如果输入的元素个数 n 是偶数，则两个堆的元素个数相等，分别取大根堆的顶和小根堆的顶，取平均值，即是所求的整个数据流的中位数；

如果输入的元素个数 n 是奇数，则必有一个堆的元素个数为（n/2+1），返回这个堆的顶，即为所求的中位数。

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        /*建立两个堆：（1）一个大根堆，保存所有整数中较小的1/2;一个小根堆，保存所有整数中较大的1/2;
          （2）并且，依次添加元素过程中，两个堆大小的差的绝对值不能超过1；*/
        
        //第一元素加入大根堆
        if(heap1.size()==0){
            heap1.push(num);
            return;
        }
        
        if(num<=heap1.top()){
            //第二个元素比大根堆的顶小
            heap1.push(num);
                
             //大根堆元素过多
            if(heap1.size()-heap2.size()>1)
            {
                int temp = heap1.top();
                heap1.pop();
                heap2.push(temp);//大根堆弹出顶到小根堆 
            }
            
        }
        else{
            //第二个元素比大根堆的顶大，直接进入小根堆
            heap2.push(num);
            
            //小根堆元素过多
            if(heap2.size()-heap1.size()>1)
            {
                int temp = heap2.top();
                heap2.pop();
                heap1.push(temp);//小根堆弹出顶到大根堆 
            }
        }
        
    }
    
    double findMedian() {
        //输入的元素为奇数个
        if(heap1.size() > heap2.size())
            return heap1.top();
        else if(heap1.size() < heap2.size())
            return heap2.top();
        
        //输入的元素个数为偶数
        else
            return (heap1.top()+heap2.top())/2.0; 
           //取大根堆、小根堆的堆顶元素取平均值，即为所求全局中位数
    }
    
private:
    priority_queue<int> heap1;//默认，大根堆
    priority_queue<int,vector<int>,greater<int>> heap2;//小根堆（升序序列）
    
};