当前位置:   article > 正文

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

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
  1. class Solution {
  2. public:
  3. void sortColors(vector<int>& nums) {
  4. int n = nums.size();
  5. int left = -1, right = n, cur = 0;
  6. while (cur < right) {
  7. if (nums[cur] == 0)
  8. swap(nums[++left], nums[cur++]);
  9. else if (nums[cur] == 2)
  10. swap(nums[--right], nums[cur]);
  11. else
  12. cur++;
  13. }
  14. }
  15. };

2、912. 排序数组

 

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

  1. class Solution {
  2. public:
  3. vector<int> sortArray(vector<int>& nums) {
  4. srand(time(NULL));
  5. qsort(nums,0,nums.size()-1);
  6. return nums;
  7. }
  8. int getRandom(vector<int>& nums,int left,int right){
  9. int i=rand();
  10. return nums[i%(right-left+1)+left];
  11. }
  12. void qsort(vector<int>& nums,int begin,int end){
  13. if(begin >= end)
  14. return;
  15. int i=begin,left=begin-1,right=end+1;
  16. int key=getRandom(nums,begin,end);
  17. while(i<right){
  18. if(nums[i]<key)
  19. swap(nums[++left],nums[i++]);
  20. else if(nums[i]>key)
  21. swap(nums[--right],nums[i]);
  22. else
  23. i++;
  24. }
  25. qsort(nums,begin,left);
  26. qsort(nums,right,end);
  27. }
  28. };

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

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

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

     <key               =key                >key
|————|————————|—————|

l          left left+1        right-1 right             r

        a                    b                        c(区间元素个数)

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应该减去这部分已经排除的元素数量。

  1. class Solution {
  2. public:
  3. int findKthLargest(vector<int>& nums, int k) {
  4. srand(time(NULL));
  5. return qsort(nums, 0, nums.size() - 1, k);
  6. }
  7. int qsort(vector<int>& nums, int l, int r, int k) {
  8. if (l == r)
  9. return nums[l];
  10. int key = getRandom(nums, l, r);
  11. int left = l - 1, right = r + 1, i = l;
  12. while (i < right) {
  13. if (nums[i] < key)
  14. swap(nums[++left], nums[i++]);
  15. else if (nums[i] > key)
  16. swap(nums[--right], nums[i]);
  17. else
  18. i++;
  19. }
  20. int c = r - right + 1, b = right - left - 1;
  21. if (c >= k)
  22. return qsort(nums, right, r, k);
  23. else if (b + c >= k)
  24. return key;
  25. else
  26. return qsort(nums, l, left, k - b - c);
  27. }
  28. int getRandom(vector<int>& nums, int left, int right) {
  29. return nums[rand() % (right - left + 1) + left];
  30. }
  31. };

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

  1. 快速选择算法(第一种方法):

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

    • 优点: 对于找到第k个最大元素,这种方法维护了一个大小为k的最小堆,时间复杂度为O(n log k),适合k远小于n的情况。
    • 缺点: 当k接近n时,性能不如快速选择算法。
      1. class Solution {
      2. public:
      3. int findKthLargest(vector<int>& nums, int k) {
      4. priority_queue<int,vector<int>,greater<int>> pq(nums.begin(),nums.begin()+k);
      5. for(size_t i=k;i<nums.size();i++){
      6. if(nums[i]>pq.top()){
      7. pq.pop();
      8. pq.push(nums[i]);
      9. }
      10. }
      11. return pq.top();
      12. }
      13. };

  3. 排序(第三种方法):

    • 优点: 实现简单,直观易懂。
    • 缺点: 时间复杂度为O(n log n),不满足题目对O(n)时间复杂度的要求。
      1. class Solution {
      2. public:
      3. int findKthLargest(vector<int>& nums, int k) {
      4. sort(nums.begin(),nums.end());
      5. return nums[nums.size()-k];
      6. }
      7. };
  4. 最大堆(第四种方法):

    • 优点: 通过构建一个最大堆,然后弹出k-1次,可以直接得到第k个最大元素。这种方法简单且对于理解堆结构很有帮助。
    • 缺点: 时间复杂度为O(n + k log n),当k较小相对高效,但当k接近n时,性能下降。
      1. class Solution {
      2. public:
      3. int findKthLargest(vector<int>& nums, int k) {
      4. priority_queue<int> pq(nums.begin(),nums.end());
      5. while(--k){
      6. pq.pop();
      7. }
      8. return pq.top();
      9. }
      10. };

结论:

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

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

4、LCR 159. 库存管理 III

思路:快速选择(快排+三指针分块+随机选择基准元素+进入对应区间寻找)
     <key               =key                >key
|————|————————|—————|

l          left left+1        right-1 right             r

        a                    b                        c(区间元素个数)

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应该减去这部分已经找到的元素数量。

  1. class Solution {
  2. public:
  3. vector<int> inventoryManagement(vector<int>& stock, int cnt) {
  4. srand(time(NULL));
  5. qsort(stock, 0, stock.size() - 1, cnt);
  6. return {stock.begin(), stock.begin() + cnt};
  7. }
  8. int qsort(vector<int>& stock, int l, int r, int cnt) {
  9. if (l == r)
  10. return stock[l];
  11. int key = getRandom(stock, l, r);
  12. int left = l - 1, right = r + 1, i = l;
  13. while (i < right) {
  14. if (stock[i] < key)
  15. swap(stock[++left], stock[i++]);
  16. else if (stock[i] > key)
  17. swap(stock[--right], stock[i]);
  18. else
  19. i++;
  20. }
  21. int a = left - l + 1, b = right - left - 1;
  22. if (a > cnt)
  23. return qsort(stock, l, left, cnt);
  24. else if (a + b >= cnt)
  25. return 0;
  26. else
  27. return qsort(stock, right, r, cnt - b - a);
  28. }
  29. int getRandom(vector<int>& stock, int left, int right) {
  30. return stock[rand() % (right - left + 1) + left];
  31. }
  32. };
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/花生_TL007/article/detail/384228
推荐阅读
相关标签
  

闽ICP备14008679号