【C++算法】45.分治_快排_数组中的第K个最大元素

题目链接：

215. 数组中的第K个最大元素

题目描述：

解法

这种题是典型的TOPK算法

TOPK算法有四种典型的问法：

1. 第K大
2. 第K小
3. 前K大
4. 前K小

基于TOPK算法有两种办法：堆排序算法O(nlogn)，快速选择算法O(n)。

算法原理：

例如第K大的元素在>key的那一段，那么<key和=key的两段都不用看了

我们分别设三个区域的元素个数为a，b，c。

C++ 算法代码：

class Solution 
{
    public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(NULL)); // 使用当前时间作为随机数生成的种子，确保每次运行程序时随机数不同
        return qsort(nums, 0, nums.size() - 1, k); // 调用快速选择函数（基于快速排序的分区思想）来查找第 k 大的元素
    }
    int qsort(vector<int>& nums, int l, int r, int k) // 快速选择函数，基于快速排序的分区思想，用于查找第 k 大的元素
    {
        if(l == r) return nums[l]; // 如果子区间的起始索引等于结束索引，说明找到了目标元素
        // 1. 随机选择基准元素
        int key = getRandom(nums, l, r); 
        // 2. 根据基准元素将数组分三块
        //    - 小于 key 的部分
        //    - 等于 key 的部分
        //    - 大于 key 的部分
        int left = l - 1, right = r + 1, i = l;
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left], nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }

        int c = r - right + 1, b = right - left - 1; // a计算大于 key 的元素数量,b计算等于 key 的元素数量
        // 3. 根据 k 的值分情况讨论：
        //    - 如果大于 key 的元素数量 c 足够大，则递归查找右边的部分
        //    - 如果等于 key 的元素数量 b 足够大，则当前 key 即为目标元素
        //    - 否则，递归查找左边的部分，调整 k 的值
        if(c >= k) return qsort(nums, right, r, k); 
        else if(b + c >= k) return key; 
        else return qsort(nums, l, left, k - b - c); //调整 k 的值为 k - b - c
    }
    int getRandom(vector<int>& nums, int left, int right) // 随机选择一个基准元素，用于快速选择
    {
        return nums[rand() % (right - left + 1) + left]; // 生成一个随机数，并将其映射到数组的索引范围内 [left, right]
    }
};