Leetcode-703- 数据流中的第 K 大元素

题目描述

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

• 请实现 KthLargest类：

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

输入：
["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

**注意:**

- 提示：
  1 <= k <= 104
  0 <= nums.length <= 104
  -104 <= nums[i] <= 104
  -104 <= val <= 104
  最多调用 add 方法 10^4 次
  题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

思路 ： 优先队列

• 使用一个大小为 k 的优先队列来存储前 k大的元素，其中优先队列的队头为队列中最小的元素，也就是第 k 大的元素。
• 在单次插入的操作中，我们首先将元素 val 加入到优先队列中。
• 如果此时优先队列的大小大于 k，我们需要将优先队列的队头元素弹出，以保证优先队列的大小为 k。

class KthLargest {
    // 1. 初始化
    PriorityQueue<Integer> pq;
    int k;
    
    // 2. 构造函数
    public KthLargest(int k, int[] nums) {
        this.k = k;
        pq = new PriorityQueue<Integer>();
        for(int x:nums){
            add(x);
        }
    }
    
    // 3. k大元素逻辑
    public int add(int val) {
        pq.offer(val);
        if(pq.size() > k){
            pq.poll();
        }
        return pq.peek();
    }
}

复杂度分析：

• 时间复杂度：O(nlogk)

• 空间复杂度：O(k) 使用大小为k的优先队列

打赏