剑指offer—数据流的中位数 解答

剑指offer—数据流的中位数

题目描述

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

思路

如果使用接收完一次排序,那么最短时间复杂度也是O(nlogn),我们需要找一种可以在接收完就可以直接返回的,也就是O(n)n次查找以内的做法,可以想到构建一颗二叉搜索树,但是二叉搜索树最好最坏情况较为不稳定,我们又可以想到使用一颗AVL树,但是AVL树代码比较复杂,我们还是找寻其他解决办法,——,想到Java有堆实现的优先级队列PriorityQueue,这不省事了吗,但是要的是中位数!!!我们无法从大根堆或者小根堆获取中位数呀,仔细一想,那不就是大根堆和小根堆的相交的地方,我们构建一个大根堆,一个小根堆,分别存储一半元素,那么最后相交的地方就可以根据奇偶判断中位数了吗!

就像两个金字塔一样,大根堆存储元素中最小的一半,小根堆存储最大的一半,小根堆的顶部就是最大的一半中最小的,大根堆堆顶就是最小的一半中最大的,那么中位数一定可以由他们两个产生,如果总长为奇数,那么就是堆元素较多的那个,如果为偶数那么就是他们之间的和除以2

一些细节的处理

  • 插入的时候如何保证一半大一半小插入

    我们需要在插入的时候维护一个计数器,每次插入就+1,如果为奇数插入到大根堆,如果为偶数就插入到小根堆。这个时候我们不能保证插入的数据均匀的按大小分布在大根堆和小根堆,我们需要在每次插入元素后进行判断,如果此时大根堆的最大的元素>小根堆最小的元素,说明这个时候元素顺序是有问题的,没有大小排(大的一半小根堆、小的一半大根堆),我们需要对元素进行交换,poll元素并互相offer进队列

  • 在进行优化:我们发现每次插入元素的时候都需要判断,这样就会耗费一些时间,如果我们有其他办法保证大小根堆顺序和元素数量符合要求并且不需要太多的判断如:每次判断的话那么业务可能就会比较慢,我们想到了每次无条件插入大根堆,如果大根堆元素比小根堆元素多两个,我们就把大根堆堆顶元素移动到小根堆,如果顺序出现问题那么我们就进行互相交换

    总结为两个核心:1.失序->交换2.大根堆多2->移动一个到小根堆

经过测试,时间复杂度会低一些,还减小了空间复杂度,不需要维护计数器

  • JDK PriorityQueue创建大小根堆,通过传入一个Comparator比较器,插入元素和当前堆中上一个元素进行比较,比较结果<0的话就需要进行交换,也就是构建的小根堆;比较结果>0的话就不需要交换,也就是构建的大根堆;

大根堆:JDK默认的是大根堆,也可以不传入比较器

new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1,Integer o2){
                return o2.compareTo(o1);
            }
        });

小根堆:

new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1,Integer o2){
                return o1.compareTo(o2);
            }
        });

代码

这是我们优化前的方法

class MedianFinder {
    private PriorityQueue<Integer> minHeap;
    private PriorityQueue<Integer> bigHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        bigHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1,Integer o2){
                return o2.compareTo(o1);
            }
        });
        minHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1,Integer o2){
                return o1.compareTo(o2);
            }
        });
    }

    int  count = 0;
    public void addNum(int num) {
        if((count&1)==0){
            bigHeap.add(num);
            count++;
        }else{
            minHeap.add(num);
            count++;
        }
        if(!bigHeap.isEmpty()&&!minHeap.isEmpty()&&minHeap.peek()<bigHeap.peek()){
            int b = bigHeap.poll();
            int m = minHeap.poll();
            minHeap.add(b);
            bigHeap.add(m);
        }
    }

    public double findMedian() {
        if((count&1)==1){
            return bigHeap.peek()*1.0;
        }else{
            return (bigHeap.peek()+minHeap.peek())/2.0;
        }
    }
}

这是我们优化后的方法,

class MedianFinder {
    private PriorityQueue<Integer> minHeap;
    private PriorityQueue<Integer> bigHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        bigHeap = new PriorityQueue<>();//默认为大根堆
        minHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1,Integer o2){
                return o1.compareTo(o2);
            }
        });
    }
    public void addNum(int num) {
        bigHeap.add(num);//每次无条件插入到大根堆
        int bl = bigHeap.size();
        int ml = minHeap.size();
        if(!minHeap.isEmpty()&&!bigHeap.isEmpty()){
            int m = minHeap.peek();
            int b = bigHeap.peek();
            if(m<b){
                minHeap.poll();
                bigHeap.poll();
                minHeap.add(b);
                bigHeap.add(m);
            }
        }
        if(ml+1<bl){
            int headFirst = bigHeap.poll();
            minHeap.add(headFirst);
        }
    }
    public double findMedian() {
        int l = bigHeap.size()+minHeap.size();
        if((l&1)==1){
            return bigHeap.peek()*1.0;
        }else{
            return (bigHeap.peek()+minHeap.peek())/2.0;
        }
    }
}