LeetCode_剑指Offer 41. 数据流的中位数(优先队列 / 大顶堆、小顶堆)

LeetCode_剑指Offer 41. 数据流的中位数(优先队列 / 大顶堆、小顶堆)

思路

针对本题,根据以上思路,可以将数据流保存在一个列表中,并在添加元素时 保持数组有序 。此方法的时间复杂度为 O(N)O(N) ,其中包括: 查找元素插入位置 O(\log N)O(logN) (二分查找)、向数组某位置插入元素 O(N)O(N) (插入位置之后的元素都需要向后移动一位)。

本题可以借助堆来进行优化
建立一个小顶堆A和大顶堆B,各自保存列表元素的一半,规定:
LeetCode_剑指Offer 41. 数据流的中位数(优先队列 / 大顶堆、小顶堆)
随后,中位数可根据A,B的堆顶元素计算得到。
LeetCode_剑指Offer 41. 数据流的中位数(优先队列 / 大顶堆、小顶堆)

整体流程

LeetCode_剑指Offer 41. 数据流的中位数(优先队列 / 大顶堆、小顶堆)

实现代码(java)

class MedianFinder {
    Queue<Integer> A, B;
    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((x, y) -> (y - x));
    }
    
    public void addNum(int num) {
        if (A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() * 1.0 : (A.peek() + B.peek()) / 2.0;
    }
}

细节解释

	Queue<Integer> A, B; 	

	A = new PriorityQueue<>();
    B = new PriorityQueue<>((x, y) -> (y - x));

这两句代码的含义是,定义一个A为优先队列,默认就是按照自然顺序排列的小顶堆,最小的元素排在最前面
而下一行的B则为修改了比较规则的大顶堆,相当于将小顶堆倒转过来,大的元素排在前面

可以替换为:B = new PriorityQueue<>(Comparator.reverseOrder())
LeetCode_剑指Offer 41. 数据流的中位数(优先队列 / 大顶堆、小顶堆)

上一篇:手写 PriorityQueue的实现 java


下一篇:PriorityBlockingQueue 分析