数据流中的第K大元素

发表于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，703. Kth Largest Element In a Stream

先看题目描述

y0Tho4.png

大意就是实现一个类，用于找到数据流中的第 K 大元素，该类中的 add 方法的功能就是加元素添加到数据流中并返回第 K 大的元素

算法和思路

小顶堆

这题不难，用小顶堆就可以解决

维护一个容量为 k 的小顶堆，然后在每次往数据流中添加元素时进行判断，若此时堆中元素个数小于 k，则直接将元素添加至小顶堆中；否则，将该元素与堆顶元素的大小进行比较，若该元素大于堆顶元素的话，才弹出堆顶元素并将该元素添加至小顶堆中，然后返回新的堆顶元素即可

算法源码

小顶堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class KthLargest {
    private int k;
    private int size;
    private PriorityQueue<Integer> prior;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.size = 0;
        this.prior = new PriorityQueue<>();
        for (int num : nums) {
            this.add(num);
        }
    }

    public int add(int val) {
        if (size < k) {
            prior.add(val);
            size++;
        } else {
            if (val > prior.peek()) {
                prior.add(val);
                prior.poll();
            }
        }
        return prior.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */