专栏首页mathor随时获取数据流的中位数

随时获取数据流的中位数

题目

有一个源源不断往外吐出整数的数据流,假设你有足够的空间来保存吐出的数。请设计一个方法,这个方法可以随时取出之前吐出所有数的中位数

要求

  1. 如果已经保存了吐出的N个数,那么任意时刻将一个新数加入的过程,其时间复杂度不超过O(logN)
  2. 取得中位数的过程,时间复杂度为O(1)

思路

建立一个大根堆,一个小根堆。每次来的一个数,和大根堆的堆顶比较,如果小于大根堆的堆顶,就加入大根堆;如果大于大根堆的堆顶,就加入小根堆

同时还要满足这两个堆中的元素个数之差不能超过2(即<2)。例如大根堆中的元素现在有3个,小根堆中的元素有1个,此时就需要把大根堆的堆顶弹出,放入小根堆中;反之也一样。注意:每次往堆中加入数的同时,也要调整堆的结构

如果吐出的数据个数为偶数,则中位数是两个堆的堆顶相加除以2;为奇数,中位数是元素个数较多的那个堆的堆顶

往堆里加入一个数的时间复杂度是O(logN),取出中位数的时间复杂度是O(1),满足题目要求

代码

import java.util.Comparator;
import java.util.PriorityQueue;

public class GetMedian {

    public static class MinHeapComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer a, Integer b) {
            return a > b ? 1 : -1;
        }
    }

    public static class MaxHeapComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer a, Integer b) {
            return b > a ? 1 : -1;
        }
    }

    public static void main(String[] args) {
        int[] arr = { 8, 3, 4, 6, 9, 7, 1 }; // 1 3 4 6 7 8 9
        double median = getMedian(arr);
        System.out.println(median);
    }

    private static double getMedian(int[] arr) {
        PriorityQueue<Integer> big = new PriorityQueue<Integer>(new MaxHeapComparator());
        PriorityQueue<Integer> small = new PriorityQueue<Integer>(new MinHeapComparator());
        for (int i = 0; i < arr.length; i++) {
            int cur = arr[i];
            if (big.isEmpty() || cur < big.peek())
                big.add(cur);
            else
                small.add(cur);
            if (big.size() - small.size() >= 2)
                small.add(big.poll());
            else if (small.size() - big.size() >= 2)
                big.add(small.poll());
        }
        if (arr.length % 2 == 0)
            return ((double) (big.peek() + small.peek()) / 2);
        else
            return big.size() > small.size() ? big.peek() : small.peek();
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 搜索(8)

    mathor
  • TRIE(2)

     其中MAX_NODE是trie中最大能存储的节点数目,CHARSET是字符集的大小,k是当前trie中包含有多少个节点。Triei的值是0表示trie树中i号...

    mathor
  • C++STL中set的使用策略(一)

    mathor
  • 流问题Flow Problem(网络最大流)- HDU 3549

    网络最大流问题属于算法 里面较难的问题,因为牵涉的概念比较多,这一篇可能需要你花比较多的时间去理解,除了看这个,最好能多参考别的书籍或者文章进行...

    ACM算法日常
  • C++那些事之static那些事

    当与不同类型一起使用时,Static关键字具有不同的含义。我们可以使用static关键字:

    公众号guangcity
  • 详解Winograd变换矩阵生成原理

    文本首发知乎:https://zhuanlan.zhihu.com/p/87516875

    Ldpe2G
  • Android自定义控件之九宫格

    Xiaolei123
  • Frogger

    思路: 以为是二分+dfs,会超时。与其这样还不如直接dfs每条路径求出max的同时,抵达终点时求min,结果还是超时。想了下,难道可以用DP做状态记录,所...

    用户1147447
  • P1855 榨取kkksc03

    题目描述 以下皆为真实的故事。 洛谷2的团队功能是其他任何oj和工具难以达到的。借助洛谷强大的服务器资源,任何学校都可以在洛谷上零成本的搭建oj并高效率的完成训...

    attack
  • 那些大厂必问的Handler和Binder,有必要去研究么?

    经常会有人问:有必要去研究Handler和Binder么?感觉工作中好像用不到呀。

    Android技术干货分享

扫码关注云+社区

领取腾讯云代金券