Leetcode刷题100天—215. 数组中的第K个最大元素(优先队列)—day15

桃扇骨 2022-09-10 14:22 152阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210823163706116][]

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4

提示：

*  1 <= k <= nums.length <= 104
 *  \-104 <= nums\[i\] <= 104

> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package 优先队列;
    
    import java.util.PriorityQueue;
    /* * 1 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ *这个题目和容易让很混淆，他要求是找出第k个最大数，而不是在k个数里面找出最大数 */
    public class _215_数组中的第K个最大元素 { 
    	public static int findKthLargest(int[] nums, int k) { 
    // 设置优先队列
    		PriorityQueue<Integer> queue=new PriorityQueue<>();
    // 将前k个数入队
    		for(int i=0;i<k;i++) { 
    			queue.add(nums[i]);
    		}
    // 通过后面数比较大小是否满足替换栈顶的要求
    		for (int i = k; i < nums.length; i++) { 
    // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
    			if (nums[i]>queue.peek()) { 
    // 出队：由于这是优先队列,所以弹出来的肯定是最小的那个数
    				queue.poll();
    // 入队
    				queue.offer(nums[i]);
    			}
    		}
    // 返回堆顶元素就是第k个最大的数
    		return queue.peek();
    	}
    	public static void main(String args[]) { 
    		int nums[]=new int[6];
    		nums[0]=5;
    		nums[1]=2;
    		nums[2]=1;
    		nums[3]=3;
    		nums[4]=6;
    		nums[5]=4;
    		int k=2;
    		int c=findKthLargest(nums, k);
    		System.out.print(c);
    	}
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210823163706116]: /images/20220829/5856e77a7ca44625b0c01a578b4b7662.png