题解 | #数据流中的中位数#

import java.util.*;
import java.math.BigDecimal;


public class Solution {

    // 创建两个小顶堆
    PriorityQueue<Integer> queue = new PriorityQueue<>(); // 存储流中的元素
    PriorityQueue<Integer> tmpQueue = new PriorityQueue<>(); // 暂存元素

    public void Insert(Integer num) {
        // 将流中的元素放入小顶堆
        // 如果元素个数为奇数，中位数为中间值；如果元素个数为偶数，则中位数为中间两个的平均值
        queue.offer(num);
        Double median = GetMedian();
        System.out.print(median + " ");
    }

    /**
     * 获取中位数
     */
    public Double GetMedian() {
        if (queue.size() % 2 == 1) {
            // 如果是奇数，弹出n-1/2，堆顶元素即为中位数
            int pollSize = (queue.size() - 1) / 2;
            for (int i = 0; i < pollSize; i++) {
                tmpQueue.offer(queue.poll());
            }
            Integer median = queue.peek();
            // 队列恢复原状
            while (!tmpQueue.isEmpty()) {
                queue.offer(tmpQueue.poll());
            }
            final BigDecimal decimal = new BigDecimal(median);
            return decimal.setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();
        } else {
            // 如果是偶数，弹出n/2-1,堆顶的两个元素的平均值即为中位数
            int pollSize = queue.size() / 2 - 1;
            for (int i = 0; i < pollSize; i++) {
                tmpQueue.offer(queue.poll());
            }
            Integer poll1 = queue.poll();
            Integer poll2 = queue.poll();
            queue.offer(poll2);
            queue.offer(poll1);
            // 队列恢复原状
            while (!tmpQueue.isEmpty()) {
                queue.offer(tmpQueue.poll());
            }
            BigDecimal decimal1 = new BigDecimal(poll1);
            BigDecimal decimal2 = new BigDecimal(poll2);
            double d1 = decimal1.setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();
            double d2 = decimal2.setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();
            return (d1 + d2) / 2;
        }
    }


}