30_703. 数据流中的第K大(小)元素
题目描述：
解题思路：
关于TopK的问题，可以使用优先队列、二叉搜索树、快速选择来解决
- 优先队列：nlogk
- 使用小根堆解决最大的K个数
- 使用大根堆解决最小的K个数
代码：
优先队列：
第K大元素
//第K大元素
class KthLargest {
private int k;
PriorityQueue pq = new PriorityQueue<>();
public KthLargest(int k, int[] nums) {
this.k = k;
int len = nums.length;
for (int i = 0; i < len; i++) {
add(nums[i]);
}
}
public int add(int val) {
pq.offer(val);
if (pq.size() > k) {
pq.poll();
}
return pq.peek();
}
}
最小的K个数
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] vec = new int[k];
if (k == 0) { // 排除 0 的情况
return vec;
}
PriorityQueue queue = new PriorityQueue(new Comparator() {
public int compare(Integer num1, Integer num2) {
return num2 - num1;
}
});
for (int i = 0; i < k; ++i) {
queue.offer(arr[i]);
}
for (int i = k; i < arr.length; ++i) {
if (queue.peek() > arr[i]) {
queue.poll();
queue.offer(arr[i]);
}
}
for (int i = 0; i < k; ++i) {
vec[i] = queue.poll();
}
return vec;
}
}