使用快速 select 算法查找第 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);
}

这是我的代码，我使用了快速select算法。在这个问题中，我的目标是获得第 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]);

使用快速 select 算法查找第 k 个最大元素

Find kth largest element using quick select algorithm

c++

data-structures

quickselect