leetcode215.数组中的第K个最大元素_给定非负数组 a ,b 和整数 k 。 求其笛卡尔积第k大元素

标签：计数排序

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

提示：- <= nums[i] <= 

思路：采用计数排序思想，创建一个涵盖所有数字可能范围的数组temp，下标i即数字，temp[i]即i出现次数，从后遍历temp，遇到temp[i]=0跳过，遇到temp[i]!=0则k--，直到k===0则找到第k大元素；注意这里nums[i]数字对应到temp是nums[i]+10000,因为如果直接对应，不处理，出现负数无法直接对应到temp下标

public int findKthLargest(int[] nums, int k) { int [] temp=new int[200001]; Arrays.fill(temp,0); for(int j=0;j0){ if(temp[a]==0) a--; else { temp[a]-=1; k--; } } return a-10000; }