数据流的中位数

2024-01-02 13:15:08

题目链接

数据流的中位数

题目描述


注意点

  • 在调用 findMedian 之前,数据结构中至少有一个元素
  • 如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值

解答思路

  • 使用两个优先队列存储数据流,其中一个优先队列队首为最大元素,另一个队首为最小元素,始终保持两个优先队列元素数量平衡,计算中位数只需要取优先队列的队首即可,不需要对其他元素进行排序

代码

class MedianFinder {
    // 队首为最小元素
    PriorityQueue<Integer> minQueue;
    // 队首为最大元素
    PriorityQueue<Integer> maxQueue;

    public MedianFinder() {
        minQueue = new PriorityQueue<>((a, b) -> (b - a));
        maxQueue = new PriorityQueue<>((a, b) -> (a - b));
    }
    
    public void addNum(int num) {
        if (minQueue.isEmpty()) {
            minQueue.offer(num);
            return;
        }
        if (num < minQueue.peek()) {
            minQueue.offer(num);
            if (minQueue.size() > maxQueue.size() + 1) {
                maxQueue.offer(minQueue.poll());
            }
        } else {
            maxQueue.offer(num);
            if (maxQueue.size() > minQueue.size()) {
                minQueue.offer(maxQueue.poll());
            }
        }
    }
    
    public double findMedian() {
        if ((minQueue.size() + maxQueue.size()) % 2 == 0) {
            return (double) (minQueue.peek() + maxQueue.peek()) / 2;
        } else {
            return minQueue.peek();
        }
    }
}

关键点

  • 优先队列加入数字时始终保持队首为最大或最小数字
  • 始终保持两个优先队列的容量大小不超过1,在计算中位数时只需要取队首的元素即可

文章来源:https://blog.csdn.net/weixin_51628158/article/details/135224525
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。