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.
题解1：玩赖的写法，直接调用java中的sort函数，之后选取倒数第k个元素，即为所有。
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
int len = nums.length;
return nums[len - k];
}
题解2：使用优先队列来实现一个小根堆。堆未满时，直接插入nums[i]；堆满了，执行poll（），先删除队列中的一个元素，在插入新元素。
在java中，常见的队列操作以及它们的区别如下所示：
| 插入 | offer | 向队列插入元素，在一个满的队列中加入一个新项会返回false。 |
| add | 向队列插入元素，在一个满的队列中加入一个新项会抛出异常。 | |
| 删除 | poll | 从队列中删除第一个元素，在队列为空时返回null。 |
| remove | 从队列中删除第一个元素，在队列为空时会抛出异常。 | |
| 查看队头元素 | peek | 在队列的头部查询元素，在队列为空时返回null。 |
| element | 在队列的头部查询元素。在队列为空时会抛出异常。 |
public int findKthLargest2(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(nums.length,(w1, w2)->w1.compareTo(w2));
for(int j=0;j<nums.length;j++){
minHeap.add(nums[j]);
if(minHeap.size()>k){
minHeap.poll();
}
}
return minHeap.peek();
}
完整代码如下：
package medium; import java.util.Arrays;
import java.util.PriorityQueue; public class L215KthLargestElementinanArray { public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
int len = nums.length;
return nums[len - k];
} public int findKthLargest2(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(nums.length, (w1, w2) -> w1.compareTo(w2));
for (int j = 0; j < nums.length; j++) {
minHeap.add(nums[j]);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
} public static void main(String[] args) {
L215KthLargestElementinanArray l215 = new L215KthLargestElementinanArray();
int[] nums = { 2, 1, 3, 4, 5 };
int k = 1;
int number = l215.findKthLargest(nums, k);
System.out.println(number);
System.out.println("!!!!!!!!!!!!");
int num2 = l215.findKthLargest2(nums, k);
System.out.println(num2);
}
}