c++ - 使用快速选择算法查找第 k 个最大元素

Question

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int partition(vector<int> &nums, int low,int high,int pivotElement)
    {
        int pivotPoint=low;
        for(int i=low;i<=high-1;i++)
        {
            if(nums[i]<=pivotElement)
            {
                swap(nums[i],nums[pivotPoint]);
                pivotPoint++;
            }
        }
        swap(nums[pivotPoint],pivotElement);
        return pivotPoint;
        
    }
    int quickSelect(vector<int> &nums, int k,int low,int high)
    {
        int pivotElement=nums[high];
        int pivot=partition(nums,low,high,pivotElement);
        if(pivot==k)
        {   
            return nums[pivot];
        }
        else if(pivot>k)
            return quickSelect(nums,k,low,pivot-1);
        else
        {   
            return quickSelect(nums,k,pivot+1,high);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
     return quickSelect(nums,nums.size()-k,0,nums.size()-1);
    }
};
int main(){
vector<int> v={3,2,1,5,6,4};
Solution ob;
cout<<ob.findKthLargest(v,2);
}

这是我的代码，我使用了快速选择算法。在这个问题中，我的目标是获得第 k 个最大的元素。尽管我试图涵盖所有内容并且通过了许多测试用例，但它在某些测试用例上给出了错误的答案。我尝试使用 cout 语句来获取错误，但根据我的试运行，我应该得到正确的输出。但是，当我尝试在第一个分区之后打印元素时，虽然 4 应该最终根据交换移动到索引 3 和 5，但那没有发生，4 仍然在最后，5 在索引 3。我无法弄清楚。请帮我解决这个问题。如果需要任何进一步的澄清，我会尽力以最好的方式解释这个问题，我很乐意提供。谢谢你。

Answer 1

swapinpartition改变了局部变量 的值pivotElement，它不会被传播回调用者。（你会得到同样的效果nums[pivotPoint] = pivotElement;。）

您需要pivotElement通过引用传递，并nums[high]直接传递nums[high]以进行更新：

int partition(vector<int> &nums, int low,int high,int &pivotElement)
// ...
// Later, in quickSelect
    int pivot=partition(nums,low,high,nums[high]);