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

数据流中的中位数

https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

#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)。

全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
码农索隆:竞争压力小,就你一个不用卷
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务