#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);
}
This is my code, I have used quick select algorithm. In this question i am aimed to get kth largest element. It is giving wrong answer on some test cases though i have tried to cover everything and many test cases are passed. I tried to use cout statement to fetch the error though as per my dry run I should have got correct output. But when I tried to print the elements after first partition though 4 should have moved to index 3 and 5 at last as per swap but that's not happening 4 is still at last and 5 at index 3. I am unable to figure that out. Kindly help me resolve this. I have tried to explain the issue in best way if any further clarification is required would be more than happy to provide. Thank you.
The swap
in partition
changes the value of the local variable pivotElement
, which will not be propogated back to the caller. (You'd get the same effect with nums[pivotPoint] = pivotElement;
.)
You need to pass pivotElement
by reference, and pass nums[high]
directly in order for nums[high]
to be updated:
int partition(vector<int> &nums, int low,int high,int &pivotElement)
// ...
// Later, in quickSelect
int pivot=partition(nums,low,high,nums[high]);