Question
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.
Code
Version 1 (sort):
public class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
Version 2 (heap):
public class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(k);
for (int i = 0; i < k; i++) {
pq.offer(nums[i]);
}
for (int i = k; i < nums.length; i++) {
if (nums[i] > pq.peek()) {
pq.poll();
pq.offer(nums[i]);
}
}
return pq.peek();
}
}
Solution
方法一：直接排序，返回倒數(shù)第k個(gè)元素即可稚照。
方法二：用小根堆。構(gòu)建一個(gè)大小為k的小根堆矿辽，返回第一個(gè)元素即可判帮。
