545. 前K大数 II

实现一个数据结构，提供下面两个接口
1.add(number) 添加一个元素
2.topk() 返回前 K 大的数

样例

s = new Solution(3);
>> create a new data structure.
s.add(3)
s.add(10)
s.topk()
>> return [10, 3]
s.add(1000)
s.add(-99)
s.topk()
>> return [1000, 10, 3]
s.add(4)
s.topk()
>> return [1000, 10, 4]
s.add(100)
s.topk()
>> return [1000, 100, 10]

思路

首先应该想到 5.第k大元素的 quickSelect 做法，但本题的数据是在变化的，所以选择 PriorityQueue 做法，本题是 PriorityQueue 的经典应用

代码

add 的时间复杂度 logK，top 的时间复杂度 KlogK

public class Solution {
    // 定义全局变量
    private int maxSize;
    private Queue<Integer> minheap;
    // 构造器
    public Solution(int k) {
        // 初始化
        minheap = new PriorityQueue<>();
        maxSize = k;
    }

    public void add(int num) {
        if (minheap.size() < maxSize) {
            minheap.offer(num);
            // 不加 return 可能会出现 minheap.size() < maxSize 却执行下面的 if 操作
            return;
        }
        
        // 在 minheap.size() == k 时执行
        if (num > minheap.peek()) {
            minheap.poll();
            minheap.offer(num);
        }
    }
 
    // 堆里总共 k 个数，每 poll 一次时间为 logK，k个数即为 KlogK
    public List<Integer> topk() {
        // 堆自带迭代器功能，取出最小堆里的值，翻转它
        Iterator it = minheap.iterator();
        List<Integer> result = new ArrayList<Integer>();
        while (it.hasNext()) {
            result.add((Integer) it.next());
        }
        Collections.sort(result, Collections.reverseOrder());
        return result;
    }
}

545. 前K大数 II

代码

推荐阅读更多精彩内容