专栏首页算法其实很好玩Day7-线性表-堆-寻找中位数

Day7-线性表-堆-寻找中位数

一 唠唠嗑

咳咳,今天是第七天了,来讲一道利用堆的,很巧,但是很简单的题

什么?你问我为什么拖更?

二 来吧!

Q:设计一个数据结构,该数据结构动态维护一组数据,且支持以下操作:

1.添加元素:void addNum(int num),将num添加进数据结构中

2.返回中位数:double findMedian(),返回其维护的中位数

中位数定义:

若数据个数为奇数,中位数是该数据排序后中间的数。

【1,2,3】,return 2

若数据个数为偶数,中位数是该数据排序后中间两个数的平均值。

【1,2,3,4】,return 2.5

三 想想呗

此时你脱口而出,这还不简单?找个数组存啊,插入一个就排序啊,排完序之后,根据数组个数找中位数呗,这种题也拿来面我,渣渣

此时的面试官狡黠一笑,哦,看起来可以,那你能不能给我一个时间复杂度为N的算法?

你:

然后面试官

好了,说正经的,显然不能这么干啊。

最好的算法是:维护一个最大堆,和最小堆

时刻保持最大堆堆顶,一直小于最小堆堆顶

且时刻保持,最大堆,与最小堆的元素个数差,<=1

这样就保持了,最大堆里存一半相对小的数,最小堆里存了一半相对大的数

取中位数的时候,根据最大堆,最小堆元素个数来判断,是取谁的堆顶元素

这样我就做到了,时间复杂度为N,即,插完,同时排完,同时取中位数为O(1)

听起来有点拗口?没关系,举个栗子就好了~

对于数组nums = 【6,10,1,7,99,4,33】

遍历进行插入我维护的“数据结构”

第一个元素,直接插最大堆

插入后最大堆【6】,最小堆【】

第二个元素,此时最大堆size(是1)> 最小堆size(是0)

即第二种情况:此时10 > 最大堆堆顶元素6,直接将10插入最小堆

插入后最大堆【6】,最小堆【10】

第三个元素,此时最大堆size(是1)= 最小堆size(是1)

即第一种情况:此时1 < 最大堆堆顶元素6,就插入最大堆

插入后最大堆【6,1】,最小堆【10】

第四个元素,此时最大堆size(是2)> 最小堆size(是1)

仍然是第二种情况:此时7 > 最大堆堆顶元素6,直接将7插入最小堆

插入后最大堆【6,1】,最小堆【7,10】

第五个元素,此时最大堆size(是2)= 最小堆size(是2)

仍然是第一种情况:此时99 > 最大堆堆顶元素6,就插入最小堆

插入后最大堆【6,1】,最小堆【7,10,99】

第六个元素,此时最大堆size(是2)< 最小堆size(是3)

即第三种情况:此时4 < 最小堆堆顶元素7,直接插入最大堆

插入后最大堆【6,1,4】,最小堆【7,10,99】

同理第七个元素,插入到最小堆。

求中位数时,逻辑简单,注释中就写的非常清晰了

需要注意的是,第二三种情况下,有逻辑,栗子中没覆盖到,大家还是动动手,体会一下为什么这样做

四 完整代码及详细注释

//
// Created by renyi on 2019-06-10.
//
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class FindMedian{
public:
    FindMedian(){//核心思想:每次插入后,最大堆堆顶,必须要小于最小堆堆顶,且插入前后,最大堆,最小堆元素个数差,要<=1
    }
    void addNum(int num){//因为最大堆元素整体小于最小堆,所以进来的第一个元素先插入最大堆
        if (more_heap.empty()){//若最大堆元素是空,即这是插第一个元素
            more_heap.push(num);//插入最大堆,然后返回,再插就走下面逻辑了
            return;
        }

        if (more_heap.size() == less_heap.size()){//当最大堆,最小堆元素个数一样时
            if (num < more_heap.top()){//当num小于最大堆堆顶时,即第一种情况
                more_heap.push(num);//直接插入最大堆
            } else{
                less_heap.push(num);//直接插入最小堆
            }
        }

        else if (more_heap.size() > less_heap.size()){//最大堆元素个数,大于最小堆元素个数
            if (num > more_heap.top()){//对应第二种情况
                less_heap.push(num);
            } else{
                less_heap.push(more_heap.top());
                more_heap.pop();
                more_heap.push(num);
            }
        }

        else if (more_heap.size() < less_heap.size()){//对应第三种情况
            if (num < less_heap.top()){
                more_heap.push(num);
            } else{
                more_heap.push(less_heap.top());
                less_heap.pop();
                less_heap.push(num);
            }
        }
    }

    double findMedian(){
        if (more_heap.size() == less_heap.size()){//当元素个数相同时,总数为偶数,中位数为中间两个数的平均数
            return (more_heap.top() + less_heap.top()) / 2;
        } else if (more_heap.size() > less_heap.size()){
            return more_heap.top();//当两者元素个数不一样,必定是奇+偶,是奇
        } else{//总数奇数个,取中间的即可
            return less_heap.top();//那么最大堆,最小堆,谁元素更多,谁的堆顶就是中间的数了
        }
    }

private:
    priority_queue<double> more_heap;//初始化一个最大堆
    priority_queue<double, vector<double>, greater<double> > less_heap;//初始化一个最小堆
};

int main(){
    FindMedian findMedian;
    int nums[] = {6, 10, 1, 7, 99, 4, 33};
    for (int i = 0; i < 7; ++i) {
        findMedian.addNum(nums[i]);
        printf("此时的中位数为:%.1f\n", findMedian.findMedian());
    }
    return 0;
}

运行结果

五 总结

好记性不如烂笔头,赶紧的动手实现吧

什么?你问我堆是什么?

那就请移步作者上一篇文章好了

本文分享自微信公众号 - 算法其实很好玩(AlgorithmBUPTrenyi),作者:BUPTrenyi

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-10

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day20-二叉树-二叉树转单链表

    这道题如果用投机取巧的办法:前序遍历二叉树,将节点push进一个vector中,再遍历vector中的节点,将相邻的节点连接上,成为单链表。面试官可能也...

    BUPTrenyi
  • Day11-字符串-无重复字符最长子串

    Q:已知一个字符串,求用该字符串的无重复字符的最长子串(有的要求求长度,今天直接求子串)

    BUPTrenyi
  • Day5-线性表-栈-最小栈问题

    而且今天本来按照之前说的,应该更两篇的,但是今天只有一篇盒饭,还不是因为最近需求排的紧,加班加点干活,大哥们见谅

    BUPTrenyi
  • PIL学习笔记(一)

    Oceanlong
  • 厚土Go学习笔记 | 27. 斐波纳契闭包

    此例我们用 go 语言的闭包实现一个斐波那契数列的返回值。 斐波那契数列,从第三个数字开始,每个数字都是前两个数字的和。 所以,我们需要在 fibonacci ...

    李海彬
  • 3D游戏开发之UE4中的集合:TSet容器

    好久没有更新了,最近一直在老家过年,网络不通的,今天才有时间更新一集。 一、TSet<T>是什么 UE4中,除了TArray动态数组外,还提供了各种各样的模板容...

    用户1198337
  • 小项目里面的大内涵

    额~因为我从没系统的看过,所以实施的时候总是出这样那样的语法问题,尤其是对 ‘ “ . ` 这些个符号的使用,非常混乱~

    libo1106
  • 为什么阿里规约手册要求谨慎使用Arrays.asList方法

    在开发中,有时候会碰到把多个参数,或者说把数组转成List的需求,通常我们会使用 Arrays.asList()方法。但是该方法在使用的过程中,稍有不慎就会出现...

    Happyjava
  • Python 爬虫简单验证码识别和抓包

    Python知识大全
  • Java &、&&、|、||、^、<<、>>、~、>>>等运算符

    无符号右移运算符和右移运算符的主要区别在于负数的计算,因为无符号右移是高位补0,移多少位补多少个0。

    萬物並作吾以觀復

扫码关注云+社区

领取腾讯云代金券