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. 暴力破解法（超时）
思路：使用排序思想
- 创建list，将数组中所有元素都添加到 list中
- 对list进行排序
- 找出 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. 优先队列法
思路：这种求第K大元素都可以使用优先队列(最大堆，最小堆)完成
最大堆
- 创建一个优先队列 PriorityQueue, 在其中添加 K 个元素
- 由于该优先队列实现是一个最小堆，所以堆顶元素一定是这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
