LeetCode.703.Kth Largest Element in a Stream 数据流中的第K大元素

题目描述

703 Kth Largest Element in a Stream
https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

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

Note:You may assume that nums’ length ≥ k-1 and k ≥ 1.

---

相似题目

LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数
LeetCode.703.Kth Largest Element in a Stream 数据流中的第K大元素
LeetCode.378.Kth Smallest Element in a Sorted Matrix 有序矩阵中第K小的元素

LeetCode.347.Top K Frequent Elements 前K个高频元素
LeetCode.剑指offer.040.数组中最小的k个数
LeetCode.023.Merge k Sorted Lists 合并K个排序链表

---

解题过程

建立一个大小为K的最小堆，用数组的前K个元素初始化，然后从第K+1个元素开始扫描数组，如果大于堆顶，则互换元素，并从上到下调整堆；如果小于堆顶，则继续读入下一个，这样最后最小堆里剩的就是最大的K个元素，堆顶是第k大元素。
时间复杂度 O(Nlogk)，空间复杂度 O(k)

private static class KthLargest {
    private int k;
    private PriorityQueue<Integer> priorityQueue; // 小顶堆

    public KthLargest(int k, int[] nums) {
        this.k = k;
        // 大小为k的小顶堆
        priorityQueue = new PriorityQueue<>(k);
        for (int i = 0; i < nums.length; i++) {
            if (i < k) {
                priorityQueue.offer(nums[i]);
            } else {
                if (nums[i] > priorityQueue.peek()) {
                    // 比堆顶（当前第k大值）大的才入堆
                    priorityQueue.poll();
                    priorityQueue.offer(nums[i]);
                }
            }
        }
    }

    public int add(int val) {
        if (priorityQueue.size() < k) {
            priorityQueue.offer(val);
        } else if (val > priorityQueue.peek()) {
            // 比堆顶（当前第k大值）大的才入堆
            priorityQueue.poll();
            priorityQueue.offer(val);
        }
        return priorityQueue.peek();
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_703_KthLargestElementInStream.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_703_KthLargestElementInStream.java

---