力扣 703. 数据流中的第 K 大元素

题目说明

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例

例1

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]

解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

例2

1
2
3
4
5
6
输入：
["KthLargest","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add"]
[[7,[-10,1,3,1,4,10,3,9,4,5,1]],[3],[2],[3],[1],[2],[4],[5],[5],[6],[7],[7],[8],[2],[3],[1],[1],[1],[10],[11],[5],[6],[2],[4],[7],[8],[5],[6]]

输出：
[null,3,3,3,3,3,3,4,4,4,5,5,5,5,5,5,5,5,6,7,7,7,7,7,7,7,7,7]

笔者理解

此题是一道设计类算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题如果用上优先队列便可很快设计完成，因为优先队列本身是一个最小生成树的结构，此时我们只需要保持优先队列的长度不变即可。

优先队列可以了解博客园Elliott_Su：https://www.cnblogs.com/Elliott-Su-Faith-change-our-life/p/7472265.html

实现

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
34
35
36
37
class KthLargest {
    final PriorityQueue<Integer> q ;
    //定义一个优先队列
    //实际上为一个最小数结构
    final int size;
    //优先队列的长度
    public KthLargest(int k, int[] nums) {
        this.size = k;
        q = new PriorityQueue<Integer>(k);
        for(int i: nums) {
            add(i);
        }
    }
    
    public int add(int val) {
        if(q.size() < size) {
            q.offer(val);
            //优先队列没有满时，直接插入
        }
        else if(q.peek() < val) {
            //如果优先队列中的最小值小于当前要插入的值
            q.poll();
            //删除当前优先队列中的最小值
            q.offer(val);
            //插入当前值
        }
        return q.peek();
        //返回当前优先队列最小值
    }
}


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

时间和空间效率都较高，可见此解法比较适合此题；

image.png

总结

本题是今天的每日一题，难度是简单，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。