Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array‘s length.
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
思路：
将nums中的前k个元素建一个“大根”堆，然后将后面[k+1,n]元素于堆顶进行比较。比堆项大，则交换、重建堆。
时间复杂度 = 第一次建堆时间 + (n-k)建堆时间（即最坏情况每次都要交换、建堆） = logk + (n-k)logk = (n-k+1)logk
java code:
public class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
for(int num : nums) {
queue.offer(num);
if(queue.size() > k) queue.poll();
}
return queue.peek();
}
}LeetCode:Kth Largest Element in an Array
原文：http://blog.csdn.net/itismelzp/article/details/51636372