使用快速选择算法查找第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

partition中的swap改变了局部变量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]);