AlgoPressAppearance
0215-数组中的第K个最大元素
https://leetcode.cn/problems/kth-largest-element-in-an-array
给定整数数组 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 <= 10^4 -10^4 <= nums[i] <= 10^4
思路
暴力法：排序后从前往后
代码
csharp
public class Solution {
public int FindKthLargest(int[] nums, int k) {
Array.Sort(nums);
return nums[nums.Length - k];
}
}
思路2：【官方】
使用快速排序的概念，做快速选择 注意 pivot 先拿出来, 判断 pIndex 是在 nums[i] < pivot 内部。
csharp
public class Solution {
public int FindKthLargest(int[] nums, int k) {
int n = nums.Length;
quickSort(nums,0,n-1, k);
return nums[n-k];
}
private void quickSort(int[] nums, int start, int end, int k){
int pIndex = partition(nums,start,end);
if(pIndex > start){
quickSort(nums,start,pIndex-1,k);
}
if(pIndex < end){
quickSort(nums,pIndex+1,end,k);
}
}
private int partition(int[] nums, int start, int end){
if(start == end){
return start;
}
Random random = new Random();
int index = random.Next(start,end);
Console.WriteLine("index={0}",index);
//swap to end
swap(nums,index,end);
//分区
int pIndex = start-1; //左边界索引
int pivot = nums[end];
for(int i=start; i<=end; i++){
if(nums[i] <= pivot){
pIndex++;
if(i > pIndex){
swap(nums,i,pIndex);
}
}
}
return pIndex;
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}