北京网站建设 标准型 新翼,可以做问卷挣钱的网站,百度信息流优化,深圳有哪些做网站公司题目描述#xff1a; 给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入…题目描述 给定整数数组 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
提示
1 k nums.length 105 -104 nums[i] 104 解决思路由于需要时间复杂度为O(n)所以传统的排序算法均不能使用。 在本题中要求获得的是第K大的元素并不要求数组要进行完全排序所以我们可以进行快速排序的变种写法 快速排序有一个特点就是在每一次进行快排之后就可以确定一个元素的最终位置 为了保证稳定性随机获取集合中的一个元素pivot进行排序所以我们可以判断比该pivot元素小的元素个数(low.size())比该pivot元素大的元素个数(above.size())以及和该pivot元素相等的元素个数(equal.size()) 此时我们所知道的是要查找第K大的元素
如果K小于above.size()时那么可以确定所需要元素在above集合中然后在above集合中进行依次变种快排如果K大于equal.size()above.size()那么说明该元素在low集合中而且是所要结果low集合中第Klow.size()-nums.size()大的元素然后再low集合中进行变种快排若以上两种情况均不满足则说明此时pivot就是我们所需要的第K大的元素
代码如下所示
class Solution {public int findKthLargest(int[] nums, int k) {ListInteger tempnew ArrayList();for(int i0;inums.length;i){temp.add(nums[i]);}return quickSort(temp,k);}public int quickSort(ListInteger temp,int k){//为了稳定性随机选择一个数Random rand new Random();int pivottemp.get(rand.nextInt(temp.size()));int i0;ListInteger lownew ArrayList();ListInteger abovenew ArrayList();ListInteger equalnew ArrayList();while(itemp.size()){if(temp.get(i)pivot){low.add(temp.get(i));}else if(temp.get(i)pivot){above.add(temp.get(i));}else{equal.add(temp.get(i));}i;}//说明第k大元素在above集合中if(kabove.size()){return quickSort(above,k);}//说明第k大元素在low集合中if(temp.size()-low.size()k){return quickSort(low,klow.size()-temp.size());}return pivot;}
}
