数据流中的中位数

古城微笑少年丶 2022-06-12 14:56 180阅读 0赞

在牛客网上刷题时遇到这道题有新解法，特此来总结下~

![这里写图片描述][SouthEast]

我开始是这么做的：

import java.util.*;
    public class Solution {
        ArrayList<Integer> a =new ArrayList<Integer>();
    
        public void Insert(Integer num) {
            if(num!=null)
                a.add(num);
        }
        public Double GetMedian() {
            Collections.sort(a);
            int len=a.size();
            int mid=len/2;
            double res=0.0;
            if(len%2!=0)
                {
                 res=a.get(mid);
            }
            else
                {
                res=(Double.valueOf(a.get(mid)+a.get(mid-1)))/2;
            }
            return res;//20ms,8664k
        }
    }

--------------------

可是看了别人的答案竟然还可以用堆来做。。。

其实是因为位于容器中的数据被中位数分成了两部分（当输入数据个数为奇数时，中位数为同一个P1=P2；为偶数时，中位数为两个P1，P2）位于容器左边的数据比右边的小。此时p1指向的是左边部分的最大数，而p2指的是右边部分的最小数。

如果能够保证数据容器左边的数都小于右边的数，这样即使左右两边内部的数据没有排序，那么也可以根据左边的最大数以及右边的最小数得到中位数。

*  关键是如何快速从一个数据容器中找到最大数？  
    **用最大堆来实现这个数据容器，因为位于堆顶的就是最大数据，最小同理。**

所以可以用一个最大堆实现左边数据容器，用最小堆实现右边的数据容器。往对重插入一个数据的时间效率是O(logn)。由于只要O(1)就可以得到位于堆顶的数据，所以得到中位数的时间效率是O(1).

**细节问题：**

首先保证数据平均分配到两个堆中，因此两个堆中的数据数目之差不能超过1。可以在数据数目为偶数时把新数据插入到最小堆中，否则插入到最大堆中。但是同时还需要保证最大堆里的数据都小于最小堆里的数据，这时需要先把这个新数据插入到最大堆中，接着把最大堆里的最大数拿出来插入到最小堆中。同理需要把一个数据插入到最大堆中。

Java的PriorityQueue 是从JDK1.5开始提供的新的数据结构接口，默认内部是自然排序，结果为小顶堆，也可以自定义排序器，比如下面反转比较，完成大顶堆。

private int count=0;
        private PriorityQueue<Integer> minHeap= new PriorityQueue<>();
        private PriorityQueue<Integer> maxHeap= new PriorityQueue<Integer>(15,new Comparator<Integer>()
                {
                    public int compare(Integer o1,Integer o2)
                    {
                        return o2.compareTo(o1);
                    }
                });
    
    public void Insert(Integer num)
    {
        count++;
        if(count%2==0)
        {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }
        else
        {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    
    }
    public Double GetMedian(){
        if(count%2==0)
            return (minHeap.peek()+maxHeap.peek())/2.0;//或者使用new Double()
        else
            return (double)(maxHeap.peek());//26,8508k
      }
    }

这里使用的是把数据为奇数时加入大顶堆，为偶数时加入小顶堆。  
制造最大堆和最小堆有数据结构可以直接使用，不用自己整了~

[SouthEast]: /images/20220612/9923ff25e0d84b85b399713d449572d4.png