本文共 983 字，大约阅读时间需要 3 分钟。

1. 本题知识点

堆

2. 题目描述

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

3. 解题思路

1. 创建一个大顶堆用于存储输入数字中较小一半，即中位数左边的一半
2. 创建一个小顶堆用于存储输入数字中较大一半，即中位数右边的一半
3. 保证大顶堆中最大的元素 < 小顶堆中最小元素，并且他们之前的元素个数相差不大于 1
4. 那么中位数就可以通过这两个堆的堆顶元素获得

4.代码

public class Solution {
       // 总个数    private int size = 0;    // 小顶堆    private PriorityQueue
   
     left = new PriorityQueue<>((o1, o2) -> o2 -o1);    // 大顶堆    private PriorityQueue
    
      right = new PriorityQueue<>();    public void Insert(Integer num) {
           if (size % 2 == 0) {
               left.offer(num);            right.offer(left.poll());        } else {
               right.offer(num);            left.offer(right.poll());        }        size++;    }    public Double GetMedian() {
           if (size % 2 == 0) {
               return (left.peek() + right.peek()) / 2.0;        } else {
               return (double) right.peek();        }    }}
    
   

转载地址：http://hdjvb.baihongyu.com/