系列专栏
目录
1、题目链接
215. 数组中的第K个最大元素 - 力扣（LeetCode）
2、题目介绍
给定整数数组 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
3、解法
解题思路
排序方法的选择：
- 虽然直观上可能会想到对整个数组进行排序然后直接取第
k个元素，但标准的排序算法（如快速排序、归并排序等）的平均时间复杂度是 O(n log n)，不满足题目要求的 O(n)。- 尝试了快排，但是会超时。
- 也可以选择快速选择算法，进行对问题的解决。
构建小堆：
- 首先，从最后一个非叶子节点（（数组长度-2）/2 ）开始调整（使用 Adjust Down），以确保每个父节点的值都大于其子节点的值。
- 这个过程称为堆化（Heapify），它将数组转换为一个最大堆。
提取第 k 个最大元素：
- 由于最大堆的根节点是数组中的最大值，我们可以通过交换根节点与最后一个元素，并减小堆的大小（即不考虑最后一个元素），然后重新调整新的根节点以保持堆的性质。
- 重复这个过程
k-1次后，根节点就会是第k个最大的元素。
4、代码
class Solution {
public:
//向下调整
//降序版
void AdjustDown(vector<int>& nums, int n, int parent)
{
//子节点必须在不越界。 child < nums.size()
int child = parent * 2 + 1;
while (child < n)
{
// 确认child指向小的那个孩子
if (child + 1 < n && nums[child + 1] < nums[child])
{
++child;
}
if (nums[parent] > nums[child])
{
swap(nums[parent], nums[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
//降序建小堆
void HeapSort(vector<int>& nums) {
//从叶子结点建堆
for (int i = (nums.size() - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(nums, nums.size(), i);
}
int end = nums.size() - 1;
while (end > 0)
{
swap(nums[0], nums[end]);
AdjustDown(nums, end, 0);
--end;
}
}
int findKthLargest(vector<int>& nums, int k) {
HeapSort(nums);
return nums[k-1];
}
};