文章482
标签257
分类63

算法:数据流中的中位数


题目名称

数据流中的中位数

如何得到一个数据流中的中位数?

如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。


分析

使用一个最大堆和一个最小堆;

保证:

  • 最大堆和最小堆数据总数之差不超过1;
  • 最大堆数值都大于最小堆数值

代码

import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {

    private Queue<Integer> minHeap = new PriorityQueue<>(15);

    private Queue<Integer> maxHeap = new PriorityQueue<>(15, (x, y) -> y - x);


    // 记录总数
    int count = 0;

    public void Insert(Integer num) {
        if ((count & 1) == 0) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
        count++;
    }

    public Double GetMedian() {
        if ((count & 1) == 0) return ((double)minHeap.peek() + maxHeap.peek()) / 2;
        return Double.valueOf(minHeap.peek());
    }
}

本文作者:Jasonkay
本文链接:https://jasonkayzk.github.io/1996/07/27/算法-数据流中的中位数/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可