C++ 快速排序&快速选择

目录

1、75. 颜色分类

2、912. 排序数组

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

4、LCR 159. 库存管理 III

1、75. 颜色分类

思路：利用快速排序思路，使用三指针分块进行优化。

• [0,left]——小于key
• [left+1,right-1]——等于key
• [right,nums.size()]——大于key

class Solution {public:void sortColors(vector& nums) {int n = nums.size();int left = -1, right = n, cur = 0;while (cur < right) {if (nums[cur] == 0)swap(nums[++left], nums[cur++]);else if (nums[cur] == 2)swap(nums[--right], nums[cur]);elsecur++;}}};

2、912. 排序数组

思路：快排+三指针优化+随机选择基准元素

class Solution {public:vector sortArray(vector& nums) {srand(time(NULL));qsort(nums,0,nums.size()-1);return nums;}int getRandom(vector& nums,int left,int right){int i=rand();return nums[i%(right-left+1)+left];}void qsort(vector& nums,int begin,int end){if(begin >= end)return;int i=begin,left=begin-1,right=end+1;int key=getRandom(nums,begin,end);while(i<right){if(nums[i]key)swap(nums[--right],nums[i]);elsei++;}qsort(nums,begin,left);qsort(nums,right,end);}};

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

思路：快速选择（快排+三指针分块+随机选择基准元素+递归排序时进入对应区间）

• 第k个最大元素也就是排序(升序)后的倒数第k个

key
|————|————————|—————|

l left left+1right-1 rightr

abc（区间元素个数）

c表示在当前key（基准值）右侧的元素数量（即比key大的元素数量），b表示等于key的元素数量。由于我们是寻找第k个最大的元素，数组的右侧代表了较大的元素。

• if (c >= k)：如果key右侧的元素数量c大于或等于k，这意味着第k个最大的元素位于key的右侧或者是key本身。因此，我们递归地在key右侧的数组部分继续进行快速选择，寻找第k个最大的元素。

• else if (b + c >= k)：如果key右侧的元素数量c加上等于key的元素数量b大于或等于k，这意味着第k个最大的元素要么是key本身，要么在等于key的这些元素中。由于这些元素都是相等的，我们可以直接返回key作为第k个最大的元素。

• else：如果上述两个条件都不满足，这意味着第k个最大的元素位于key的左侧。因此，我们递归地在pivot左侧的数组部分继续进行快速选择。此时，我们需要调整k的值，因为我们已经排除了b + c个比key大或等于key的元素，所以新的k应该减去这部分已经排除的元素数量。

class Solution {public:int findKthLargest(vector& nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}int qsort(vector& nums, int l, int r, int k) {if (l == r)return nums[l];int key = getRandom(nums, l, r);int left = l - 1, right = r + 1, i = l;while (i < right) {if (nums[i]  key)swap(nums[--right], nums[i]);elsei++;}int c = r - right + 1, b = right - left - 1;if (c >= k)return qsort(nums, right, r, k);else if (b + c >= k)return key;elsereturn qsort(nums, l, left, k - b - c);}int getRandom(vector& nums, int left, int right) {return nums[rand() % (right - left + 1) + left];}};

为了找到数组中第k个最大的元素，并且要求时间复杂度为O(n)，我们可以比较这些方法：

1. 快速选择算法（第一种方法）:

   • 优点: 平均时间复杂度为O(n)，符合题目要求。它通过随机选择一个枢轴来分割数组，然后只在包含第k个最大元素的那部分数组上递归，从而减少了不必要的计算。
   • 缺点: 最坏情况下的时间复杂度为O(n^2)，但这种情况很少发生。算法的性能依赖于随机数的选择。

2. 最小堆（第二种方法）:

   • 优点: 对于找到第k个最大元素，这种方法维护了一个大小为k的最小堆，时间复杂度为O(n log k)，适合k远小于n的情况。
   • 缺点: 当k接近n时，性能不如快速选择算法。

     class Solution {public:int findKthLargest(vector& nums, int k) {priority_queue<int,vector,greater> pq(nums.begin(),nums.begin()+k);for(size_t i=k;ipq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();}};

3. 排序（第三种方法）:

   • 优点: 实现简单，直观易懂。
   • 缺点: 时间复杂度为O(n log n)，不满足题目对O(n)时间复杂度的要求。

     class Solution {public:int findKthLargest(vector& nums, int k) {sort(nums.begin(),nums.end());return nums[nums.size()-k];}};

4. 最大堆（第四种方法）:

   • 优点: 通过构建一个最大堆，然后弹出k-1次，可以直接得到第k个最大元素。这种方法简单且对于理解堆结构很有帮助。
   • 缺点: 时间复杂度为O(n + k log n)，当k较小相对高效，但当k接近n时，性能下降。

     class Solution {public:int findKthLargest(vector& nums, int k) {priority_queue pq(nums.begin(),nums.end());while(--k){pq.pop();}return pq.top();}};

结论:

• 如果你追求平均情况下的最优时间复杂度，并且可以接受在极少数情况下性能的不确定性，快速选择算法是最佳选择。
• 如果k值较小，最小堆方法也是一个不错的选择，因为它可以较快地找到第k个最大的元素。
• 排序方法虽然简单，但不满足题目对时间复杂度的要求。
• 最大堆方法适用于k值较小的情况，但当k值较大时，性能不是最优的。

综上所述，考虑到时间复杂度的要求和算法的效率，快速选择算法是最符合题目要求的解决方案

4、LCR 159. 库存管理 III

思路：快速选择（快排+三指针分块+随机选择基准元素+进入对应区间寻找）
key
|————|————————|—————|

l left left+1right-1 rightr

abc（区间元素个数）

a表示在当前的key（基准值）左边的元素数量，b表示等于key的元素数量。cnt是我们需要找到的库存余量最少的商品数量。

• if (a > cnt)：如果key左边的元素数量a大于cnt，这意味着我们需要的cnt个最小元素全部位于key的左边。因此，我们递归地在key左边的数组部分继续进行快速选择，寻找这cnt个最小元素。

• else if (a + b >= cnt)：如果key左边的元素数量a加上等于key的元素数量b大于或等于cnt，这意味着我们需要的cnt个最小元素已经包含在左边的元素和等于key的元素中。由于题目说明返回顺序不限，我们不需要进一步排序或选择，可以直接返回结果。

• else：如果上述两个条件都不满足，这意味着我们需要的cnt个最小元素部分位于key的右边。因此，我们递归地在key右边的数组部分继续进行快速选择。此时，我们需要调整cnt的值，因为我们已经找到了一部分所需的最小元素（即a + b个），所以新的cnt应该减去这部分已经找到的元素数量。

class Solution {public:vector inventoryManagement(vector& stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() + cnt};}int qsort(vector& stock, int l, int r, int cnt) {if (l == r)return stock[l];int key = getRandom(stock, l, r);int left = l - 1, right = r + 1, i = l;while (i < right) {if (stock[i]  key)swap(stock[--right], stock[i]);elsei++;}int a = left - l + 1, b = right - left - 1;if (a > cnt)return qsort(stock, l, left, cnt);else if (a + b >= cnt)return 0;elsereturn qsort(stock, right, r, cnt - b - a);}int getRandom(vector& stock, int left, int right) {return stock[rand() % (right - left + 1) + left];}};