整数数组中寻找第K大元素
算法思想
使用最大堆结构,最大堆的顶部总是最大元素。因此我们只需要构建一个最大堆,然后循环取K次堆顶就可以拿到目标元素。
堆是什么,怎么使用堆,这里不做讨论。
算法复杂度分析
构建堆:O(N)
取出K个元素,K常数,算法复杂度O(N)
上代码
import java.util.*;
public class Finder {
PriorityQueue<Integer> maxHeap;
public int findKth(int[] a, int n, int K) {
// write code here
createHeap(a, n);
int val = 0;
for(int i=0; i<K; i++){
val = maxHeap.poll();
}
return val;
}
public void createHeap(int[] a, int n){
maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
...