LeetCode hot100-74

https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-100-liked

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

这题的解法在leetcode评论区里找的

这个快排写得比较简洁。是从大到小排的。就找前面的第k-1个位置就行。用rand作为枢纽也可以加速。

class Solution {Random rand=new Random();public int findKthLargest(int[] nums, int k) {return quickSort(nums,k,0,nums.length-1);}private int quickSort(int[] nums,int k,int left,int right){int index=rand.nextInt(right-left+1)+left;int flag=nums[index];nums[index]=nums[left];int i=left,j=right;while (i<j){while (i<j&&nums[j]<=flag) j--;nums[i]=nums[j];while (i<j&&nums[i]>=flag) i++;nums[j]=nums[i];}nums[i]=flag;if (i==k-1) return nums[i];else if (i<k-1) return quickSort(nums,k,i+1,right);else return quickSort(nums,k,left,i-1);}
}