# 6ms c++ code Quicksort

• ``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
if(nums.size()<k) return 0;
if(nums.size()==0) return 0;
int end = (int)nums.size()-1;
int start = 0;
int pivot = getPivot(nums, start, end);
while (pivot+1!=k) {
if(pivot<k) start = pivot+1;
if(pivot>k) end = pivot-1;
pivot = getPivot(nums, start, end);
}
return nums[pivot];
}

int getPivot(vector<int>& nums, int start, int end) {
int temp;
if(start==end) return start;
int i=start,j=i+1;
while (j<=end) {
if(nums[j]>nums[start]) {
i++;
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
j++;
}
temp = nums[start];
nums[start] = nums[i];
nums[i] = temp;
return i;
}
};``````

• why so complex?

``````int quickSelect(vector<int>& nums, int start, int end, int k) {
int pivot = nums[end], j = start;
for (int i = start;i < end;++i)
if (nums[i] > pivot)
swap(nums[i],nums[j++]);
swap(nums[j],nums[end]);
if (k == j-start+1) return nums[j];
if (k < j-start+1) return quickSelect(nums,start,j-1,k);
else return quickSelect(nums,j+1,end,k-j+start-1);
}

int findKthLargest(vector<int>& nums, int k) {
return quickSelect(nums,0,nums.size()-1,k);
}``````

• my 4ms c++

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int start=0,end=int(nums.size())-1;
int pivot=getPivot(nums,start,end);
while (pivot+1!=k) {
if(pivot<k) start = pivot+1;
if(pivot>k) end = pivot-1;
pivot = getPivot(nums, start, end);
}
return nums[pivot];
}
int getPivot(vector<int>& nums,int start,int end)
{
if(start==end) return start;
int i=start,j=i+1;
int temp;
while(j<=end)
{
if(nums[j]>nums[start])
{
++i;
temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
++j;
}
temp=nums[i];
nums[i]=nums[start];
nums[start]=temp;
return i;
}
};``````

• you don't have to do one more swap after the for cycle, just leave the pivot at the end and move on with the rest.

• thanks! according to your suggestion, the code becomes:

``````int quickSelect(vector<int>& nums, int start, int end, int k) {
int pivot = nums[end], j = start;
for (int i = start;i < end;++i)
if (nums[i] > pivot)
swap(nums[i],nums[j++]);
if (k == j-start+1) return nums[end];
if (k < j-start+1) return quickSelect(nums,start,j-1,k);
else return quickSelect(nums,j,end-1,k-j+start-1);
}

int findKthLargest(vector<int>& nums, int k) {
return quickSelect(nums,0,nums.size()-1,k);
}``````

• Beautiful~, vote for your solution :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.