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

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

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

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

示例:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

说明:

你可以假设 nums 的长度≥ k-1 且k ≥ 1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth--element-in-a-stream/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 1. 暴力破解法（超时）

思路：使用排序思想

1. 创建list，将数组中所有元素都添加到 list中
2. 对list进行排序
3. 找出 list 中第 K 大的元素

private int k;
    private List<Integer> list;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            add(nums[i]);
        }
    }

    public int add(int val) {
        list.add(val);
        Collections.sort(list);
        return list.get(list.size() < k ? 0 : list.size() - k);
    }

复杂度分析：

• 时间复杂度：O(n ^ 2), 在遍历数组过程中需要对list进行排序

• 空间复杂度：O(k), list 所占用的空间大小

• 2. 优先队列法

该问题类似于LeetCode 347. 前 K 个高频元素 - 简书

思路：这种求第K大元素都可以使用优先队列(最大堆，最小堆)完成

最大堆

1. 创建一个优先队列 PriorityQueue, 在其中添加 K 个元素
2. 由于该优先队列实现是一个最小堆，所以堆顶元素一定是这3个中的最小值，如果要添加的这个数大于堆顶元素，那么直接进行替换
3. 替换完成之后，这个优先队列中一定存储这数组中前 K 大的元素，而我们要找的元素 K 就是堆顶元素

private int k;
    private PriorityQueue<Integer> queue;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        //创建优先队列, 底层实现是一个最小堆
        queue = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            add(nums[i]);
        }
    }

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

复杂度分析：

• 时间复杂度：O(n + log(k)), 其中堆中添加元素时间复杂度为 O(log(k))

• 空间复杂度：O(k), 优先队列中只用存储 K 个元素

• 测试用例

public static void main(String[] args) {
         int[] nums = {4, 5, 8, 2};
         System.out.println("nums:" + Arrays.toString(nums));
         KthLargest kthLargest = new KthLargest(3, nums);
         System.out.println("数据流中的第K大元素:" +  kthLargest.add(3));
    }

• 结果

nums:[4, 5, 8, 2]
数据流中的第K大元素:4

---

• 源码

• 我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github