在未排序的数组中找到第 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
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
针对这个题目，我们首先想到的就是先用排序算法对数据从大到小进行排序，然后直接返回降序后的第 K 个元素即可。
另外，我们也可以借鉴快速排序的思想。每次选取一个 pivot，将大于 pivot 的数放在 pivot 左边，将小于 pivot 的数放在 pivot 右边。
这时候，如果 pivot 正好是第 K 个数据，则 pivot 就是数组中的第 K 个最大元素。
image.png
如果 pivot 所在的位置小于 K ，则说明数组中的第 K 个最大元素位于 pivot 的右边。此时，假设 pivot 的位置为 which_max，which_max 是几就代表 pivot 是数组中的第几个最大元素。这时候，我们再从 pivot 右边的数据中找到第 (K-which_max) 个最大元素即可。
image.png
如果 pivot 所在的位置大于 K ，则说明数组中的第 K 个最大元素位于 pivot 的左边。这时候，pivot 左边的数据全部大于 pivot，我们继续从 pivot 左边的数据中找第 K 个最大元素即可。
image.png
public int findKthLargest(int[] nums, int k) {
return quickSortRecursion(nums, 0, nums.length - 1, nums.length - k);
}
public int quickSortRecursion(int[] nums, int left, int right, int k) {
if (left >= right) {
return nums[left];
}
int pivot = quickSortPartition(nums, left, right, k);
if (pivot == k) {
return nums[pivot];
}
if (k > pivot) {
return quickSortRecursion(nums, pivot + 1, right, k);
} else {
return quickSortRecursion(nums, left, pivot - 1, k);
}
}
Random random=new Random();
//对 nums[left...right] 进行partition操作 使得
// nums[left...partitionIndex]>val nums[partitionIndex+1...right]<val
public int quickSortPartition(int[] nums, int left, int right, int k) {
//增加随机
int pivot = random.nextInt(right - left + 1) + left;
swap(nums, pivot, left);
int val = nums[left];
pivot=left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] < val) {
//相同索引 避免swap
if((pivot+1)!=i) {
swap(nums, pivot + 1, i);
}
pivot++;
}
}
swap(nums, left, pivot);
return pivot;
}
private void swap(int[] nums, int source, int target) {
int temp = nums[source];
nums[source] = nums[target];
nums[target] = temp;
}
