寻找中位数

LeetCode 295. Find Median from Data Stream 设计一个数据结构,该数据结构动态维护一组数据,且支持如下操作: 1.添加元素: void addNum(int num),将整型num添加至数据结构中。 2.返回数据的中位数: double findMedian(),返回其维护的数据的中位数。 中位数定义: 1.若数据个数为奇数,中位数是该组数排序后中间的数。[1,2,3] -> 2 2.若数据个数为偶数,中位数是该组数排序后中间的两个数字的平均值。[1,2,3,4] -> 2.5

class MedianFinder{
public:
    MedianFinder(){
    }
    void addNum(int num){//将数据结构中添加一个整数
    }中位数
    double findMedian(){//返回该数据结构中维护的数据
     }
};
思考与分析

如何获取中位数? 存储结构使用数组,每次添加元素或查找中位数时对数组排序, 再计算结果

时间复杂度

1.若添加元素时排序,addNum复杂度O(n),findMedian复杂度O(1) 2.若查询中位数时排序,addNum复杂度O(1),findMedian复杂度 O(nlogn)

若添加元素或查询中位数是随机的操作,共n次操作,按上述思想,整体复 杂度最佳为O(n^2),是否还有更好的方法?

算法设计,巧用堆的性质

动态维护一个最大堆与一个最小堆,最大堆存储一半数据,最小堆存储 一半数据,维持最大堆的堆顶比最小堆的堆顶小,即可解决该问题。

获取中位数
情况1:最大堆与最小堆元素个数相同时:
情况2:最大堆比最小堆多一个元素
情况3:最大堆比最小堆少一个元素:
void addNum(int num){//big_queue最大堆,small_queue最小堆
    if(big_queue.empty()){
        big_queue.push(num);
        return;
    }
    if(big_queue.size() == small_queue.size()){
        if(num < big_queue.top()){
            big_queue.push(num);
        }
        else{
            small_queue.push(num);
        }
    }
    else if(big_queue.size() > small_queue.size()){
         if(num > big_queue.top()){
             small_queue.push(num);
          }
         else{
            small_queue.push(big_queue.top());
        big_queue.pop();
        big_queue.push(num);  
        }
    }
    else if(big_queue.size() < small_queue.size()){
         if(num < small.top()){
             big_queue.push(num);  
         }   
          else{
              big_queue.push(small_queue.top());
    small_queue.pop;
    small_queue.push(num);
          }
    }
}
double findMedian(){
    if(big_queue.size() == small_queue.size()){
        return (big_queue.top() +small_queue.top()) /2;
    } 
    else if (big_queue.size() > small_queue.size()){
        return big_queue.top();
    }
    return small_queue.top();
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python爬虫与数据挖掘

Python大神用一道题带你搞定Python函数中形参和实参问题

昨天在Python学习群里有位路人甲问了个Python函数中关于形参和实参一个很基础的问题,虽然很基础,但是对于很多小白来说不一定简单,反而会被...

15910
来自专栏IMWeb前端团队

神奇运算符

每一门编程语言的设计都离不开运算符,我们写的每一行代码基本也少不了它们,这篇文章就让我们一起来了解一下这个无处不在的小伙伴的应用和小技巧吧~~ ~ 按位取反 字...

23390
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第7章 面向对象编程(OOP)(1)第7章 面向对象编程(OOP)《Kotlin极简教程》正式上架:

在前面的章节中,我们学习了Kotlin的语言基础知识、类型系统、集合类以及泛型相关的知识。在本章节以及下一章中,我们将一起来学习Kotlin对面向对象编程以及函...

11020
来自专栏企鹅号快讯

Python数据类型之字符串第三季

Python字符串的格式化 大家可能也已经看到了 字符串在本系列课程中 常老师已经和大家一起探讨了好几节课了 何时为什么呢?? 大家别嫌磨叽(同音可能不同字)啊...

20390
来自专栏AzMark

Python列表与元组

19630
来自专栏C语言及其他语言

《黄老师问答笔录》之C语言常见易错问题

以下摘自黄老师课堂课堂答疑、与学生交流的真实问题总结,为了便于入学者学习查阅,总结归纳于此。 1、问:我想判断一个数字是否在一个区间里,比如if(90<a<10...

381130
来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(5) - 选择排序

14240
来自专栏落影的专栏

leetcode––为求职为生的编程网站

前言 leetcode是一个在线编程网站,题目源于各大公司的面试、有各种解法、多语言和在线测试支持; 我们扫一眼leetcode上的Company:Googl...

423100
来自专栏向治洪

Scala入门

Scala入门 Scala简介 ps:在最新的薪资调查中,Scala程序员的工资是平均最高的Scala工资。 Scala是一门多范式的编程语言,一种类似java...

21870
来自专栏斑斓

当函数成为一等公民时,设计模式的变化

GOF提出的设计模式,其本质思想是封装变化。故而,创建型模式封装的是对象创建的变化,结构型模式封装的是对象之间的协作与组合结构,行为型模式则封装了对象行为的变化...

33650

扫码关注云+社区

领取腾讯云代金券