leetcode刷题记录（八十七）——215. 数组中的第K个最大元素
（一）问题描述
215. 数组中的第K个最大元素 - 力扣（LeetCode）215. 数组中的第K个最大元素 - 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 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 <= 105 * -104 <= nums[i] <= 104
https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-100-liked
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 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 <= 105-104 <= nums[i] <= 104
（二）解决思路
方法一：堆排序
如果没学习过堆排序的话建议看这个视频数据结构合集 - 堆与堆排序(算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili，讲得很详细。这道题的解法没什么特殊的，就是堆排序，用大顶堆，排到第k-1个就停止，此时堆顶的元素就是第k个最大值。
复杂度分析
- 时间复杂度：O(nlogn)，建堆的时间代价是 O(n)，删除的总代价是 O(klogn)，因为 k<n，故渐进时间复杂为 O(n+klogn)=O(nlogn)。
- 空间复杂度：O(logn)，即递归使用栈空间的空间代价。
class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize=nums.length;
//建堆，其实就是从第一个非叶子节点开始（因为叶子节点已经满足堆的条件了），比较节点和左右叶子的大小关系并取较大值交换，直到节点在合适的位置上
//最后一个非叶节点下标是heapSize/2-1
for(int i=heapSize/2-1;i>=0;i--){
maxHeapify(nums,i,heapSize);
}
//排序
//处理k-1次之后的栈顶元素就是结果
for(int i=nums.length-1;i>=nums.length-k+1;i--){
//从堆顶元素开始处理，栈顶元素是当前最大的元素，每次和未排列的最后一个元素交换
//排列好的元素都在数组尾部，从小到大排列
swap(nums,0,i);
//排列好的元素不再考虑
heapSize--;
maxHeapify(nums,0,heapSize);
}
return nums[0];
}
public void maxHeapify(int[] nums,int i,int heapSize){
//建堆i从0开始，所以左叶子是2i+1，右叶子是2i+2
int left=2*i+1, right=2*i+2, largest=i;
//如果i比left小，i往下换
//这里的写法很巧妙，既能判断nums[i]与左右孩子的大小关系，又能取左右孩子较大的一个
if(left<heapSize&&nums[largest]<nums[left]){
largest=left;
}
if(right<heapSize&&nums[largest]<nums[right]){
largest=right;
}
if(largest!=i){
//需要交换
swap(nums,i,largest);
//继续处理下一轮，直到叶子节点或者它大于左右孩子了
maxHeapify(nums,largest,heapSize);
}
}
public void swap(int[] nums,int i, int largest){
int temp=nums[i];
nums[i]=nums[largest];
nums[largest]=temp;
}
}方法二：快速排序
如果没学习过快速排序建议看这个视频数据结构合集 - 快速排序(算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili。这道题就是用k来判断一下接下来排左区间还是右区间，不用整个全排，从而减少一些操作，降低时间复杂度到O(n)
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(logn)，递归使用栈空间的空间代价的期望为 O(logn)。
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;
}
}
//如果k<=j，说明枢轴在k右边，将左半边排序
if (k <= j) return quickselect(nums, l, j, k);
//如果k>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);
}
}