打卡第十一天～

题目描述

• 虽然但是，这是一道很nice的题目（涉及的知识点、运用很实用，见知识点模块）
  
  

知识点

1. 优先队列

• priorityQueue 是 Queue 接口的实现，可以对其中元素进行排序。
• 默认顺序是升序；采用的是堆排序（小顶堆），因此只能保证根是最值，整个堆并不是有序的。
• 自定义比较类：在 priorityQueue 的构造函数参数中用 Lambda 表达式表示即可。

2. Java 中 queue 的 offer、poll 等区别

• add、offer：都是添加；队满情况 add 抛出异常，而 offer 则返回 false，可用于判断
• remove、poll：都是删除首元素；队空情况remove抛出异常，而 poll 返回 null
• element、peek：都是查询首元素；队空情况element抛出异常，而peek 返回 null

思路 && 代码

• 代码量不大，主要考察的思路～
• 首先中位数需要考虑总数奇偶情况：奇取中值，偶取平均值。
• 然后既然想获得好的时间复杂度，那就空间换时间了（否则数组慢慢来也行了）
• 接着，既然中位数是在排序后元素集的中间，那么我们可以有这么一个考虑：中间靠两个数据结构实现（毕竟一半一半嘛！），而有序（或局部有序）的数据结构中，进行 add 操作的时间复杂度最低的(O(logn))就是堆了！
• 因此，我们选取优先队列来作为实现的数据结构～
• 主要思路：大顶堆存储较小部分，小顶堆存储较大部分。通过两个堆的堆顶来取中位数。通过先添加到堆a，再添加堆a的堆顶到堆b的“洗元素”方式来维护较大、较小的属性。

class MedianFinder {
    Queue<Integer> smallHeap, bigHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        // 各存一半：small 小顶堆存储较大部分；big 大顶堆存储较小部分
        smallHeap = new PriorityQueue<>();
        bigHeap = new PriorityQueue<>((x, y) -> (y - x));
    }
    
    // 维护两个 Heap 的较大、较小属性：O(logn)
    public void addNum(int num) {
        // N = 奇数：增加 bigHeap 元素，通过先添加到 smallHeap，再获取其堆顶实现
        if(smallHeap.size() != bigHeap.size()) {
            smallHeap.add(num);
            bigHeap.add(smallHeap.poll());
        } 
        // N = 偶数：增加 small 元素，通过先添加到 bigHeap，再获取其堆顶实现
        else {
            bigHeap.add(num);
            smallHeap.add(bigHeap.poll());
        }
    }
    
    // O(1)
    public double findMedian() {
        // 偶数情况
        if(smallHeap.size() == bigHeap.size()) {
            // 较大堆的最小值 + 较小堆里的最大值
            return (smallHeap.peek() + bigHeap.peek()) / 2.0;
        }
        // 奇数情况
        else {
            return smallHeap.peek();
        }
    }
}

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

二刷

• 关键词：优先队列、堆之间洗数据、Lambda 表达式
• 思路还是难忘，代码也不多。这道题保持 hard 的时间估计不长了…

class MedianFinder {
    Queue<Integer> smallTop = new PriorityQueue<>();
    Queue<Integer> bigTop = new PriorityQueue<>((x, y) -> (y - x));

    public MedianFinder() {}
    
    public void addNum(int num) {
        if(smallTop.size() == bigTop.size()) {
            bigTop.add(num);
            smallTop.add(bigTop.poll());
        }
        else {
            smallTop.add(num);
            bigTop.add(smallTop.poll());
        }
    }
    
    public double findMedian() {
        if(smallTop.size() == bigTop.size()) {
            return (smallTop.peek() + bigTop.peek()) / 2.0;
        }
        else {
            return smallTop.peek();
        }
    }
}