题目链接

215. 数组中的第K个最大元素 - 力扣（LeetCode）

题目解析

算法原理

解法一:

直接理由java内部的排序函数,Arrays.sort()进行排序, 然后我们直接返回第k个最大的元素

nums[nums.length-k]

解法二:

使用堆

我们先把所有元素丢到大根堆里面,然后取k次堆顶元素

PriorityQueue<Integer> heap = new PriorityQueue<>((a,b)->b-a);

解法三: 

三指针法, 数组分三块

代码编写

解法一:

class Solution {public int findKthLargest(int[] nums, int k) {// 排序Arrays.sort(nums);return nums[nums.length - k];}
}

解法二:

class Solution {public int findKthLargest(int[] nums, int k) {// 利用大根堆PriorityQueue<Integer> heap = new PriorityQueue<>((a,b)-> b-a);// 把元素放进大根堆for(int x : nums){heap.offer(x);}// 取第k个while(--k != 0){heap.poll();}return heap.poll();}
}

解法三

class Solution {// 交换private static void swap(int[] nums, int index1, int index2) {int tmp = nums[index1];nums[index1] = nums[index2];nums[index2] = tmp;}// 递归，分三段private static int quickSort(int[] nums, int l, int r, int k) {// l, r 是用来固定左右端点的int left = l - 1;int right = r + 1;// 获取区间中间的元素作为 keyint key = nums[(l + r) / 2];  // 修改这里，取中间的值// 数组分成四段// [l,left]<key,[left+1,i]==key,[i+1,right-1]未知,[right,r]>key;int i = l;  // 从区间的开始进行遍历while (i < right) {// 如果是 < keyif (nums[i] < key) {swap(nums, ++left, i++);} else if (nums[i] == key) {// 如果是 == keyi++;} else {// 如果是 > keyswap(nums, --right, i);}}// 此时分成三块: [l, left]<key [left + 1, right - 1]==key [right, r]>key// 分类讨论 [l, left] [left + 1, right - 1] [right, r]int b = (right - 1) - (left + 1) + 1;  // 中间部分的长度int c = r - right + 1;  // [right, r] 部分的长度if (c >= k) {// 去 [right, r] 查找第 k 大return quickSort(nums, right, r, k);} else if ((b + c) >= k) {// 如果中间部分就是第 k 大，直接返回return key;} else {// 去 [l, left] 查找第 k - b - c 大return quickSort(nums, l, left, k - b - c);}}public int findKthLargest(int[] nums, int k) {return quickSort(nums, 0, nums.length - 1, k);}
}

为什么是k-b-c大? 下面是ai的解释
在快速排序（Quick Sort）中，我们通过分区操作将数组分为三部分：

1.小于基准值（key）的部分
2.等于基准值的部分
3.大于基准值的部分

我们希望找到第 k 大的元素。在快速排序的过程中，我们每次选择一个基准值（key）并进行分区，接下来，我们递归地在其中一部分继续查找目标元素。
问题核心
假设我们有一个 k 值，表示我们要找到第 k 大的元素。在分区后，数组被分为三部分：

[l, left] 这部分元素都小于基准值 key
[left + 1, right - 1] 这部分元素等于基准值 key
[right, r] 这部分元素都大于基准值 key

我们已经知道，在这些分区中，key 的位置非常关键。接下来，我们就要根据 k 和这些部分的大小来决定递归的方向。
代码逻辑解释
考虑下面几个变量：

b：等于 key 的元素的个数。
c：大于 key 的元素的个数。

那么，b + c 是右边部分（即大于 key 的部分加上等于 key 的部分）的元素总数。
如果 k 大于 b + c，意味着我们要找的第 k 大的元素不在右边（即大于 key 的部分和等于 key 的部分），而是在左边（小于 key 的部分）。因此，我们递归地去左边查找。
但是，左边的部分有一些特殊情况需要考虑：

左边的部分包含了所有小于 key 的元素，因此找第 k 大的元素时，要跳过这些小于 key 的元素。
1由于已经知道有 b 个元素等于 key，而且右边有 c 个大于 key 的元素，所以我们实际需要在左边找的是第 k - b - c 大的元素。

为什么是 k - b - c

我们已经知道：
c 是大于 key 的元素数量。

b 是等于 key 的元素数量。
因此，如果我们要找的是第 k 大的元素，在递归调用时，要在左边查找的是：
去掉 c 个大于 key 的元素，
去掉 b 个等于 key 的元素，
所以我们要查找的是 第 k - b - c 大的元素。

总结

k 是我们要找的第 k 大的元素。
b 是等于 key 的元素个数。
c 是大于 key 的元素个数。

因此，在左边查找时，我们要寻找的元素是第 k - b - c 大的元素，原因是我们已经排除了右边部分的元素（大于 key 和等于 key 的部分）。

二刷

class Solution {//交换void swap(int[] nums, int index1, int index2) {int tmp = nums[index1];nums[index1] = nums[index2];nums[index2] = tmp;}int quickSort(int[] nums, int l, int r, int k) {// 定义移动边界int left = l - 1;int right = r + 1;int key = nums[(right + left) / 2];// 遍历int i = l;while (i < right) {// 数组分四块if (nums[i] < key) {// 去左边swap(nums, i++, ++left);} else if (nums[i] == key) {// 直接往后走i++;} else {// 去右边swap(nums, i, --right);}}// 此时分为三块:[l,left]<key [left+1,right-1]=key [right,r]>key// 去找第k个最大的元素int b = (right - 1) - (left + 1) + 1; //中间部分int c = r - right + 1; // 右边部分if (c >= k) {// 说明第k个最大在右边部分return quickSort(nums, right, r, k);} else if ((b + c) >= k) {// 说明第k个最大在中间部分return key;} else {// 说明第k个最大在左边部分，调整kreturn quickSort(nums, l, left, k - b - c);}}public int findKthLargest(int[] nums, int k) {// 使用快排来找到数组中第k个最大元素return quickSort(nums, 0, nums.length - 1, k);}
}