数组中第K大的数字
LeetCode215数组中的第K个最大元素。给定整数数组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
我们在后面堆的部分也会分析这个问题，这里看看如何基于快速排序来做。而且要直接改造一下上面的快排来解决，而不是另起炉灶，只有这样平时的练习才有效果。
那为什么能用快速排序来解决呢？我们还是看上面排序的序列：{26,53,48,15,13,48,32,15}
第一次选择了26为哨兵，进行一轮的排序过程为：
上面红框位置表示当前已经被赋值给了pivot或者其他位置，可以空出来放移动来的新元素了。可以看到26最终被放到了属于自己的位置上，不会再变化，而26的左右两侧可以分别再进行排序。
这里还有一个关键信息，我们可以知道26的索引为3，所以递增排序之后26一定是第4大的元素。这就是解决本问题的关键，既然知道26是第4大，那如果我要找第2大，一定是要到右边找。如果要找第6大，一定要到左边找（当然，如果降序排序就反过来了)，而不需要的那部分就不用管了。这就是为什么能用快速排序解决这个问题。
力扣官方题解：
class Solution {
int quickselect(int[] nums, int l, int r, int k) {
if (l == r) return nums[k];
int x = nums[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
if (k <= j) return quickselect(nums, l, j, k);
else return quickselect(nums, j + 1, r, k);
}
public int findKthLargest(int[] _nums, int k) {
int n = _nums.length;
return quickselect(_nums, 0, n - 1, n - k);
}
}
自己写的快排
class Solution {
int quicksort(int[] nums, int left, int right, int pos){
if(left >= right) return nums[pos];
int pivot = nums[right];
int i = left - 1;
if(left < right){
for(int j = left; j < right; j++){
if(nums[j] < pivot){
int temp = nums[j];
i++;
nums[j] = nums[i];
nums[i] = temp;
}
}
}
int pivotnum = i + 1;
int temp = nums[pivotnum];
nums[pivotnum] = nums[right];
nums[right] = temp;
if(pivotnum >= pos) return quicksort(nums, left, pivotnum - 1, pos);
else return quicksort(nums, pivotnum + 1, right, pos);
}
public int findKthLargest(int[] nums, int k) {
int left = 0, right = nums.length - 1;
int pos = nums.length - k;
return quicksort(nums, left, right, pos);
}
}
自己一开始偷懒的代码
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
