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

这道题我在做北京的一家教诲公司的笔试时出现过，且标题里直接要求利用快排做，以是我也利用快排做的。
标题： 

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请留意，你必要找的是数组排序后的第 k 个最大的元素，而不是第 k 个差异的元素。
你必须计划并实现时间复杂度为 O(n) 的算法办理此标题。
示例 1:

2. <strong>输入:</strong> [3,2,1,5,6,4], k = 2
3. <strong>输出:</strong> 5

复制代码

示例 2:

2. <strong>输入:</strong> [3,2,3,1,2,4,5,5,6], k = 4
3. <strong>输出:</strong> 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不小于基准，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函数的结果。
  

代码：

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

复制代码