# [recommend for beginners]clean C++ implementation with detailed explanation

• ``````  4 ms solution
``````

CODE:

``````   class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//max heap method
//min heap method
//order statistics
make_heap(nums.begin(), nums.end());
int result;
for(int i=0; i<k; i++){
result=nums.front();
pop_heap(nums.begin(), nums.end());
nums.pop_back();
}
return result;
}
};
``````

20MS solution

code:

``````   class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
/** priority_queue<int, vector<int>, less<int>> q; **/
priority_queue<int, vector<int>> q;
int len=nums.size();
for(int val:nums){
q.push(val);
}
while(q.size() > len-k+1){
q.pop();
}
return q.top();
}
};
``````

200ms solution

code:

``````  class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int left=0, right=nums.size()-1;
while(true){
int pos=help(nums, left, right);
if(pos==k-1)  return nums[pos];
if(pos>k-1)   right=pos-1;
else left=pos+1;
}
}

/*** return-the-position-of-the-left-element-in-the-partitioned-list ***/
int help(vector<int>& nums, int left, int right){
int pivot=nums[left];
int l=left+1, r=right;
/*** swap-the-element-to-make-the-left-bigger-right-smaller ***/
while(l<=r){
if(nums[l]<pivot && nums[r]>pivot)
swap(nums[l++], nums[r--]);
if(nums[l]>=pivot) l++;
if(nums[r]<=pivot) r--;
}
/*** r-is-biggest-position-smaller-than-pivot ***/
swap(nums[left], nums[r]);
return r;
}
};``````

• I do think the key part is that how to update

`````` pos>k-1   left=pos+1
pos<k-1   right=pos-1
``````

Code :

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int left=0, right=nums.size()-1;
while(true){
/*** return pivot position ***/
int pos=help(nums, left, right);
/** found position **/
if(pos==k-1)  return nums[pos];
/** the bigger contains more number **/
if(pos>k-1)  right=pos-1;
/** the smaller contains more number **/
else left=pos+1;
}
}

/*** quick-sort-based-pivot-function ***/
int help(vector<int>& nums, int left, int right){
int pivot=nums[left];
int l=left+1, r=right;
while(l<=r){
/*** move the bigger number left and smaller number right ***/
if(nums[l]<pivot && nums[r]>pivot)   swap(nums[l++], nums[r--]);
if(nums[l]>=pivot)  l++;
if(nums[r]<=pivot)  r--;
}
/*** swap the pivot ***/
swap(nums[left], nums[r]);
return r;
}
};``````

• The third solution is really cool !!

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