剑指offer题解--②数据流中的中位数

题目描述

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

题解

首先想到的就是可以用大顶堆小顶堆来解决这个问题；但是队列好久没有使用了，那就得复习一下队列的一些常用方法:
增加:
①add(): 增加一个元索 (如果队列已满，则抛出一个IIIegaISlabEepeplian异常 )
②put(): 添加一个元素 (如果队列满，则阻塞)
③offer(): 添加一个元素并返回true (如果队列已满，则返回false)
移除:
①remove(): 移除并返回队列头部的元素 (如果队列为空，则抛出一个NoSuchElementException异常)
②take(): 移除并返回队列头部的元素 (如果队列为空，则阻塞)
③poll(): 移除并返问队列头部的元素 (如果队列为空，则返回null)
获取:
①element(): 返回队列头部的元素 (如果队列为空，则抛出一个NoSuchElementException异常)
②peek(): 返回队列头部的元素 (如果队列为空，则返回null)

解题思路

大顶堆存放小的数字，从大到小排序、小顶堆存放大的数字，从小到大排序:
用一个count记录当前的次数，从0开始，偶数个的时候先进入大顶堆，然后弹出第一个到小顶堆；奇数个的时候，先进入小顶堆，然后弹出第一个到大顶堆；
读数时:当两个堆的大小一致时，取两者的平均数；当大顶堆大于小顶堆的大小时，返回大顶堆的头部；当小顶堆大小大于大顶堆时，返回小顶堆的头部；

代码演示

    // 小顶堆
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    // 大顶堆
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2) ->o2 -o1);
    // 记录当前次数 从0开始
    private int count = 0;
    public void Insert(Integer num) {
        if (count % 2 == 0){
            maxHeap.offer(num);
            int max = maxHeap.poll();
            minHeap.offer(max);
        }else {
            minHeap.offer(num);
            int min = minHeap.poll();
            maxHeap.offer(min);
        }
        count ++ ;
    }

    public Double GetMedian() {
        if (minHeap.size() == maxHeap.size()){
            return (double) (minHeap.peek() + maxHeap.peek()) / 2.0;
        }else if (minHeap.size() < maxHeap.size()){
            return maxHeap.peek() / 1.0;
        }else{
            return minHeap.peek() / 1.0;
        }
    }