一、题目内容
题目要求给定一个整数数组 nums 和一个整数 k，返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
二、题目分析
输入和输出
输入：
一个整数数组
nums。一个整数
k。
输出：
一个整数，表示数组中第 k 个最大的元素。
算法逻辑
使用快速选择算法（Quick Select）来解决这个问题。快速选择算法是基于快速排序算法的变种，用于在 O(n) 的平均时间复杂度内找到数组中的第 k 大元素。
初始化：
定义一个辅助函数
partition，用于将数组划分为两部分，左边的元素都小于等于某个基准值，右边的元素都大于基准值。定义主函数
quickSelect，用于递归地找到第 k 大的元素。
划分数组：
在
partition函数中，选择数组的最后一个元素作为基准值。遍历数组，将小于等于基准值的元素移到数组的左边，大于基准值的元素移到右边。
返回基准值的最终位置。
递归查找：
在
quickSelect函数中，根据基准值的位置与目标索引 k 的关系，决定是继续在左边子数组查找，还是在右边子数组查找。如果基准值的位置正好是目标索引 k，则返回基准值。
终止条件：
当基准值的位置等于目标索引 k 时，返回该位置的值。
三、解题要点
快速选择算法的定义
快速选择算法是基于快速排序算法的变种，用于在 O(n) 的平均时间复杂度内找到数组中的第 k 大元素。它通过划分数组，逐步缩小搜索范围，直到找到目标元素。
算法复杂度
时间复杂度： O(n)，在平均情况下，每次划分可以将问题规模减半。
空间复杂度： O(1)，只需要常数级别的额外空间。
四、代码解答
以下是使用快速选择算法的 C++ 实现代码：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 转换为第 k 小的元素（从 0 开始计数）
k = nums.size() - k;
return quickSelect(nums, 0, nums.size() - 1, k);
}
private:
// 快速选择算法
int quickSelect(vector<int>& nums, int left, int right, int k) {
if (left == right) return nums[left];
int pivotIndex = partition(nums, left, right);
if (k == pivotIndex) {
return nums[k];
} else if (k < pivotIndex) {
return quickSelect(nums, left, pivotIndex - 1, k);
} else {
return quickSelect(nums, pivotIndex + 1, right, k);
}
}
// 划分数组
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j < right; ++j) {
if (nums[j] <= pivot) {
swap(nums[i], nums[j]);
++i;
}
}
swap(nums[i], nums[right]);
return i;
}
};五、详细注释
快速选择算法的作用
快速选择算法用于在 O(n) 的平均时间复杂度内找到数组中的第 k 大元素。它通过划分数组，逐步缩小搜索范围，直到找到目标元素。
算法逻辑
划分数组：
在
partition函数中，选择数组的最后一个元素作为基准值。遍历数组，将小于等于基准值的元素移到数组的左边，大于基准值的元素移到右边。
返回基准值的最终位置。
递归查找：
在
quickSelect函数中，根据基准值的位置与目标索引 k 的关系，决定是继续在左边子数组查找，还是在右边子数组查找。如果基准值的位置正好是目标索引 k，则返回基准值。
终止条件
当基准值的位置等于目标索引 k 时，返回该位置的值。
六、代码执行过程示例
假设我们有 nums = [3, 2, 1, 5, 6, 4] 和 k = 2。
代码执行过程：
初始化：
k = nums.size() - k = 6 - 2 = 4，目标是找到第 4 小的元素。
划分数组：
初始调用
quickSelect(nums, 0, 5, 4)。partition(nums, 0, 5)：选择
nums[5] = 4作为基准值。遍历数组，将小于等于 4 的元素移到左边，大于 4 的元素移到右边。
最终数组变为
[3, 2, 1, 4, 6, 5]，基准值 4 的位置是 3。返回基准值的位置 3。
递归查找：
因为基准值的位置 3 < 4，继续在右边子数组查找。
调用
quickSelect(nums, 4, 5, 4)。partition(nums, 4, 5)：选择
nums[5] = 5作为基准值。遍历数组，将小于等于 5 的元素移到左边，大于 5 的元素移到右边。
最终数组变为
[3, 2, 1, 4, 5, 6]，基准值 5 的位置是 4。返回基准值的位置 4。
返回结果：
基准值的位置 4 == 目标索引 4，返回
nums[4] = 5。
最终结果：第 2 大的元素是 5。
七、总结
快速选择算法的作用
快速选择算法用于在 O(n) 的平均时间复杂度内找到数组中的第 k 大元素。它通过划分数组，逐步缩小搜索范围，直到找到目标元素。
算法复杂度
时间复杂度： O(n)，在平均情况下，每次划分可以将问题规模减半。
空间复杂度： O(1)，只需要常数级别的额外空间。
算法逻辑
划分数组：
选择基准值，将数组划分为两部分。
返回基准值的最终位置。
递归查找：
根据基准值的位置与目标索引 k 的关系，决定是继续在左边子数组查找，还是在右边子数组查找。
如果基准值的位置正好是目标索引 k，则返回基准值。
终止条件
当基准值的位置等于目标索引 k 时，返回该位置的值。