剑指Offer（六十三）-- 数据流中的中位数

秦怀杂货店

发布于 2022-02-15 14:07:57

2130

发布于 2022-02-15 14:07:57

文章被收录于专栏：技术杂货店

Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution

题目描述

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

思路以及解答

用一个数字来不断统计数据流中的个数，并且创建一个最大堆，一个最小堆，如果插入的数字的个数是奇数的时候，让最小堆里面的元素个数比最大堆的个数多1，这样一来中位数就是小顶堆的堆顶，如果插入的数字的个数是偶数的时候，两个堆的元素保持一样多，中位数就是两个堆的堆顶的元素相加除以2。

代码如下：

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    private int count = 0;
    private PriorityQueue<Integer> min = new PriorityQueue<Integer>();
    private PriorityQueue<Integer> max = new PriorityQueue<Integer>(new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    public void Insert(Integer num) {
        count++;
        if (count % 2 == 1) {
            // 奇数的时候，需要最小堆的元素比最大堆的元素多一个。
            // 先放到最大堆里面，然后弹出最大的
            max.offer(num);
            // 把最大的放进最小堆
            min.offer(max.poll());
        } else {
            // 放进最小堆
            min.offer(num);
            // 把最小的放进最大堆
            max.offer(min.poll());
        }
    }

    public Double GetMedian() {
        if (count % 2 == 0) {
            return (min.peek() + max.peek()) / 2.0;
        } else {
            return (double) min.peek();
        }
    }

}

空间复杂度为O(n)，取出中位数的时间复杂度为O(1)。

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-29，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法