剑指offer-数据流中的中位数(大顶堆和小顶堆)
2020-04-17 本文已影响0人
棉花糖7
这道题官方题解两种方法
1.利用库函数，二分法进行查找lower_bound
2.利用有限队列，维护两个堆，大顶堆和小顶堆
题目
code
核心要点：设置两个优先队列，分别存数据流前半部分和后半部分，前半部分用大顶堆存，后半部分用小顶堆存。
添加num：先添加到大顶堆（前半部分），再把大顶堆首移入小顶堆，判断一下前半部分是否长于后半部分，如是则把小顶堆首移入大顶堆。
找中位数：若前半部分长于后半部分（共有奇数个num），返回大顶堆首；否则返回大小顶堆首的平均值。
