剑指offer63数据流中的中位数

剑指offer63
牛客其他博客参考

题目分析:
数据流动态不断插入，找数据流中位数
1、暴力解法--不断排序
时间复杂度：Insert: O(1) GetMdeian: O( nlog(n) ) 空间复杂度：O(n)
个人代码

//暴力方法 --不断排序 取中
    vector<int>v;
    void Insert(int num) {
        v.push_back(num);
    }

    double GetMedian() { 
        sort(v.begin(),v.end());
        if((v.size()&1)==1)
        {
            return v[v.size()/2];
        }
        else
        {
            return (v[v.size()/2]+v[(v.size()-1)/2])/2.0;
        }
    }

2、插入排序
个人代码

class Solution {
public:
    //插入排序-- 因为数据流一个个进入，所以可以选择插入排序，每次插入一个元素,
    //要插入的序列是有序的，也就是说数据流插入n个数，时间只是进行了一次插入排序
    //实际：无论插入还是暴力都无意义，只要插入时放入合适位置(每次插入的思想遍历一遍)，
    //      GetMedian中并不需要排序，时间复杂度一致，优化无意义
    vector<int>v;
    void Insert(int num) {
        if(v.empty())
            v.push_back(num);
        else //把元素插入合适位置，为了避免插入时需要移位，遍历两遍，用插入排序思想，从后往前遍历找位置
        {
            v.push_back(num);
            int i=v.size()-2;
            for(i=v.size()-2;i>=0;i--)
            {
                if(v[i]>num)
                {
                    v[i+1]=v[i]; //后移
                }
                else
                    break;
            }
            v[i+1]=num;
        }
    }

    double GetMedian() { 
        if((v.size()&1)==1)
            return 1.0*v[v.size()/2];
        else
            return (v[v.size()/2]+v[(v.size()-1)/2])/2.0;
    }

};

3、经典方法-- 大顶堆、小顶堆
[3]:https://www.nowcoder.com/profile/396966893/codeBookDetail?submissionId=110233652
[个人代码参考][3]
同时建立一个大顶堆（根节点最大），小顶堆（根节点最小），保持大顶堆小顶堆数据数量平衡，大顶堆放入数据较小值，小顶堆放入数据较大值，这样最后中位数取值完全由大顶堆和小顶堆的根节点值确定
数据流元素经过小顶堆筛选后（筛选出当前小顶堆最小值）插入大顶堆，每次插入都检查大顶堆小顶堆中元素数量是否平衡（差值超过1），不平衡则大顶堆的根节点弹出插入小顶堆，这样始终保持：1、大顶堆元素数量=大顶堆元素数量+1，或者大顶堆元素数量=大顶堆元素数量
2、大顶堆始终是所有数据中较小的一半元素，小顶堆始终是所有数据中较大的一半元素
时间复杂度：insert: O（logn） GetMdeian: O（1）
空间复杂度：insert: O（n） GetMdeian: O（1）
即 n个元素的数据流插入取中位数的实际复杂度 ：O(nlogn) ,空间复杂度：O(n)
知识补充：priority_queue'

自定义类型情况：

转载链接

class Solution {
public:
    priority_queue<int>bigMap;//或者priority_queue<int,vector<int>,less<int>>bigMap;
    priority_queue<int,vector<int>,greater<int>>smallMap;//小顶堆，存放较大值
    void Insert(int num) {
        smallMap.push(num);
        bigMap.push(smallMap.top()); //经小顶堆筛选后，先插入大顶堆
        smallMap.pop();
        if((bigMap.size()-smallMap.size())>1) //检查是否平衡，不平衡调整
        {
            smallMap.push(bigMap.top());
            bigMap.pop();
        }
    }

    double GetMedian() { 
        double n1=static_cast<double>(bigMap.top()); //较小
        double n2=static_cast<double>(smallMap.top()); //较大值
        if(bigMap.size()==smallMap.size()) //偶数个元素
            return (n1+n2)/2.0;
        else
            return n1;
    }
};