欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[leetCode]剑指 Offer 41. 数据流中的中位数

程序员文章站 2024-02-13 14:04:52
...

[leetCode]剑指 Offer 41. 数据流中的中位数

最大堆,最小堆

 由于需要使用一个数据容器保存从数据流中得到的数据,那么对该容器插入数据与读取数据的时间复杂度有一定要求。
 假设数据在容器中已排序,那么使用两个指针即可得到中位数,当数据量为奇数时p1,p2指向同一个数据。
[leetCode]剑指 Offer 41. 数据流中的中位数
 如果数据量为偶数,p1指向左边最大数,p2指向右边最小数。
[leetCode]剑指 Offer 41. 数据流中的中位数
因此可以将数据分为两部分:

  • 左半部分
  • 右半部分

左半部分应小于等于右半部分。由于需要快速找到左半部分的最大数与右半部分的最小数,可以想到使用最大堆最小堆。由于要保证左右两部分数据量之差不超过1,所以可以在数据总量为偶数时将新数据插入最小堆,数据总量为奇数时将数据插入最大堆。
 如果新插入最小堆的数据比最大堆的最大数据要小。因为最小堆数据要大于最大堆数据,所以需要新数据插入最大堆,将最大堆的最大数据插入最小堆。同理新插入最大堆的数据大于最小堆最小数据时,应将新数据插入最小堆,将最小堆最小数据插入最大堆。
 代码如下:

class MedianFinder {

    private PriorityQueue<Integer> minPQ;

    private PriorityQueue<Integer> maxPQ;

    /** initialize your data structure here. */
    public MedianFinder() {
        this.minPQ = new PriorityQueue<>(600);//初始化容量
        this.maxPQ = new PriorityQueue<>(600,new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
    }
    
    public void addNum(int num) {
        if(((minPQ.size() + maxPQ.size()) & 1) == 0){//数据总量为偶数,把新数据插入最小堆
            if(maxPQ.size() > 0 && num < maxPQ.peek()){//最小堆的数据>最大堆数据
                maxPQ.offer(num);//新数据插入最大堆
                num = maxPQ.poll();
            }
            minPQ.offer(num);//取出最大堆最大数据加入最小堆
        }else{//数据总量为奇数插入最大堆
            if(minPQ.size() > 0 && num > minPQ.peek()){
                minPQ.offer(num);
                num = minPQ.poll();
            }
            maxPQ.offer(num);
        }
    }
    
    public double findMedian() {
        int size = minPQ.size() + maxPQ.size();
        if(size == 0)
            throw new RuntimeException("No numbers are available");
        double median = 0;
        if((size & 1) == 1)
            median = minPQ.peek();
        else
            median = (minPQ.peek() + maxPQ.peek())/2.0;
        return median;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
相关标签: LeetCode