从大数据中找到TopK个数,比较经典的就是维护一个小根堆,堆顶是堆中最小的元素,每次通过移除堆顶,重新堆排序来维护这个结构。
每次判断队列顶端元素和新元素大小决定是否入队,当超过维护的上限时移除堆顶元素。
public static void findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minQueue = new PriorityQueue<>(k);
for (int num : nums) {
if (minQueue.size() < k || num > minQueue.peek())
minQueue.offer(num);
if (minQueue.size() > k)
minQueue.poll();
}
for(int i=0;i<k;i++){
System.out.println(minQueue.poll());
}
}