215. Kth Largest Element in an A
2016-12-26 本文已影响0人
FlynnLWang
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
方法一:直接排序,返回倒数第k个元素即可。
方法二:用小根堆。构建一个大小为k的小根堆,返回第一个元素即可。