给定整数数组
nums
和整数k
,请返回数组中第k
个最大的元素。请注意,你需要找的是数组排序后的第
k
个最大的元素,而不是第k
个不同的元素。输入:[3,2,1,5,6,4] 和
k = 2 输出: 5
提到数组中最大元素,我们往往想到就是先给数组进行排序,然后取最大值,现在我们按照这个思路写一写代码
- 首先判断入参是否合法
f (nums == null || nums.length == 0) {
return 0;
}
- 然后对数组进行排序
Arrays.sort(nums);//默认排序方法时双基准快排,效率较高
- 因为我们取的是第k个最大的元素
因为数组的长度是6,而k是2,我们所需要求的值的索引刚好是4,所以我们可以得出我们所需要推出的值是nums.length-k(在做题的过程中,如果需要确定关系式的这种情况,个人建议还是举出例子,然后亲自推导比较好一点)
return nums[nums.length - k];
接下来,提到最大值,大家还能想到什么方法?是不是有种数据结构,特能自动的为我们进行数值的排序,不错,就是优先队列 ,我们可以先将数组中的元素都往优先队列中塞进去,然后poll k次就是我们所需要的值,我们直接上代码
public int findKthLargest(int[] nums, int k) {
if(nums==null||nums.length==0){
return 0;
}
//对比较器进行重写,从大到小,因为PriorityQueue的默认排序时升序排序
PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->{
return b -a;});
for(int num:nums){
queue.offer(num);
}
int res=0;
while(k>0){
res=queue.poll();
k--;
}
return res;
}