日做力扣题2--215. 数组中的第K个最大元素-CSDN博客

本文链接：https://blog.csdn.net/ouyfg/article/details/145739324

这道题我在做北京的一家教育公司的笔试时出现过，且题目里直接要求使用快排做，所以我也使用快排做的。

题目：

给定整数数组 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

思路：

快速选择算法的基本思想是通过选择一个“基准”（pivot）元素，将数组分成两部分：一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。然后，根据k的值，递归地在包含第k大元素的那一部分继续执行，直到找到第k大的元素。

设置两个函数：

`quickselect()：`

函数逻辑：

基准情况处理：如果左边界等于右边界，意味着当前考虑的数组段仅包含一个元素。尽管此时k的值并不重要（因为只有一个元素可选），但为了保持递归逻辑的一致性，我们仍返回nums[k]。在实际应用中，更清晰的写法是直接返回nums[l]，但这里的写法在逻辑上仍然无误。
选择基准元素：我们选取左边界的元素nums[l]作为基准。同时，初始化两个指针i和j，分别指向左边界的左侧（i = l - 1）和右边界的右侧（j = r + 1）。
分区过程：通过两个do-while循环，我们将数组划分为两部分。循环结束时，所有小于基准的元素都将位于基准的左侧，而所有大于基准的元素则位于其右侧。指针i和j在循环中逐步逼近，直至相遇。若它们相遇前指向的元素满足交换条件（即i < j，且nums[i]不小于基准，nums[j]不大于基准），则交换这两个元素。
递归搜索：分区完成后，我们根据k的值决定递归搜索的方向。由于我们寻找的是第k大的元素，且数组是按从大到小的顺序“假设排序”的，因此：
- 若k <= j，说明第k大的元素位于基准的左侧或就是基准本身，于是我们在左半部分继续搜索。
- 若k > j，说明第k大的元素位于基准的右侧，于是我们在右半部分继续搜索

`findKthLargest():`

函数逻辑：

计算数组大小：首先，我们计算数组nums的大小n。
调用quickselect函数：由于quickselect函数期望的k参数是基于0的索引，而题目要求的k是基于1的排名，因此我们需要将k转换为对应的索引值。这通过n - k实现，因为排序后的数组中第k大的元素将位于索引n - k处（数组从0开始索引）。
返回结果：quickselect函数返回第k大的元素的值，我们将其直接返回作为findKthLargest函数的结果。

代码：

class Solution {
public:
    // 快速选择算法，用于找到数组中第k大的元素
    int quickselect(vector<int>& nums, int l, int r, int k) {
        // 基本情况：如果左边界等于右边界，说明只剩一个元素，直接返回该元素
        if (l == r)
            return nums[k]; // 注意这里的k实际上是一个误导，因为当l==r时，k的值并不重要，返回nums[l]即可
        // 但由于我们的递归调用中k表示的是目标元素的索引（基于0），所以这里为了保持一致也写为nums[k]，
        // 实际上在l==r的情况下，这个k值会被忽略，因为只会有一个元素被返回。
        // 更好的做法是返回一个明确的值或者修改函数签名以避免这种混淆。
        // 然而，在这个特定的实现中，由于我们总是确保k对应于目标元素的索引（在递归调用中），
        // 所以这里的写法在逻辑上仍然是正确的（尽管有些混淆）。
        
        // 选择基准元素（这里选择左边界的元素），并初始化两个指针
        int partition = nums[l], i = l - 1, j = r + 1;
        
        // 通过两个do-while循环，将数组中小于基准的元素移动到左边，大于基准的元素移动到右边
        while (i < j) {
            do i++; while (nums[i] < partition); // 找到第一个不小于基准的元素
            do j--; while (nums[j] > partition); // 找到第一个不大于基准的元素
            
            // 如果找到了这样的两个元素，则交换它们
            if (i < j)
                swap(nums[i], nums[j]);
        }
        
        // 此时，基准元素的位置j（或j+1，取决于你如何定义分区）可以用来判断第k大的元素在哪一部分
        // 由于我们是从大到小排序（找第k大），所以基准元素及其左边的元素都是不小于它的，
        // 而右边的元素都是小于它的。因此，如果k <= j，说明第k大的元素在基准的左边或就是基准本身；
        // 如果k > j，说明第k大的元素在基准的右边。
        
        // 递归地在包含第k大元素的那一部分继续寻找
        if (k <= j) // 注意这里的j是分区后基准元素所在的位置（也是最后一个不小于基准的元素的位置）
            return quickselect(nums, l, j, k); // 在左半部分继续寻找
        else
            return quickselect(nums, j + 1, r, k); // 在右半部分继续寻找
    }
    
    // 找到数组中第k大的元素
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        // 由于题目要求的是第k大的元素，而我们的quickselect函数是基于0索引的，
        // 所以我们需要将k转换为对应的索引值，即n-k（因为数组是从0开始索引的）。
        return quickselect(nums, 0, n - 1, n - k);
    }
};