整数数组中寻找第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 ...
执行时间: 29.725074768066 毫秒