题解 | #数据流中的中位数#

#include <algorithm>
#include <list>
class Solution {
public:
    void Insert(int num) {
        if(tmp.size() == 0){
            tmp.push_back(num);
        }else{
            auto ite = tmp.end();
            ite --;
            while(ite != tmp.begin()){
                if(*ite > num){
                    ite --;
                }else{
                    tmp.insert(++ite,num);
                    return;
                }
            }
            if(*ite > num){
                tmp.insert(ite,num);
            }else{
                tmp.insert(++ite,num);
            }
            // auto ite = lower_bound(tmp.begin(),tmp.end(), num);
            // tmp.insert(ite,num);
        }
    }

    double GetMedian() {
        double res; 
        if(tmp.size() % 2 == 1){
            int move = tmp.size() / 2;
            auto ite = tmp.begin();
            while(move > 0){
                ite ++;
                move --;
            }
            res = *ite;
            return res;
        }else{
            double res2;
            int move = tmp.size() / 2;
            auto ite = tmp.begin();
            while(move > 0){
                ite ++;
                move --;
            }
            res = *ite;
            ite--;
            res2 = * (ite);
            res = (res + res2) / 2;
            return res;
        }
    }

    list<int> tmp;
};

该题使用在插入的时候使用插入排序，使用双向链表去保存插入的节点，每次插入，先查找到它的位置，然后插入，如果链表为空直接插入，时间复杂度是O(n)。在搜索中位数的时候，先获取到链表大小，如果大小为奇数，那么就大小除2，然后获得的值为迭代器从begin开始偏移的位数；当大小为偶数，那么就取其中值和中值的右一位的和除二。时间复杂度也是O(n)。保存元素所花费的空间是O(n)。