LeetCode Hot100 295.数据流的中位数

2023-12-21 22:48:44

题目

中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

  • 例如?arr = [2,3,4]?的中位数是?3?。
  • 例如?arr = [2,3]?的中位数是?(2 + 3) / 2 = 2.5?。

实现 MedianFinder 类:

  • MedianFinder() 初始化?MedianFinder?对象。

  • void addNum(int num)?将数据流中的整数?num?添加到数据结构中。

  • double findMedian()?返回到目前为止所有元素的中位数。与实际答案相差?10-5?以内的答案将被接受。

思路

class MedianFinder {
    PriorityQueue<Integer> minHeap; // 小顶堆存储的是比较大的元素,堆顶是其中的最小值
    PriorityQueue<Integer> maxHeap; // 大顶堆存储的是比较小的元素,堆顶是其中的最大值

    public MedianFinder() {
        this.minHeap = new PriorityQueue<>();
        this.maxHeap = new PriorityQueue<>((a, b) -> b - a);
    }
    
    public void addNum(int num) {
        // 第一个元素进minHeap
        // 小顶堆存储的是比较大的元素,num比较大元素中最小的还大,所以,进入minHeap
        if (minHeap.isEmpty() || num > minHeap.peek()) {
            minHeap.offer(num);
            // 如果minHeap比maxHeap多2个元素,就平衡一下
            if (minHeap.size() - maxHeap.size() > 1) 
                maxHeap.offer(minHeap.poll());
        } else {
            maxHeap.offer(num);
            // 这样可以保证多的那个元素肯定在minHeap
            if (maxHeap.size() - minHeap.size() > 0) {
                minHeap.offer(maxHeap.poll());
            }
        }
    }
    
    public double findMedian() {
        boolean flag = minHeap.size() > maxHeap.size(); // true表示总共奇数个数,false表示偶数个数  
        if (flag)
            return minHeap.peek();
        else
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

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