# 3 C++ solutions (O(NlogN) sort, O(klogN) heapsort, O(n) average quicksort-kind )

• First version, using std::sort, and return the k-th (from the end) entry

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
return nums[nums.size()-k];
}
};
``````

Second version, using a heap, and pop up k-1 entries, the left top one is what we need

``````int findKthLargest(vector<int>& nums, int k) {
make_heap(nums.begin(), nums.end());
for(auto i=0; i<k-1;i++)
{
pop_heap(nums.begin(), nums.end());
nums.pop_back();
}
return nums.front();
``````

Third one, do quicksort, use the first entry as pivot and divide the array in two parts, the first half is the one no less than pivot and the second half is the one less then pivot. Then based on the length of the first half, decide to proceed in which half.

``````int findKthLargest(vector<int>& nums, int k) {
int i, m,n, pivot, head =0, tail=nums.size()-1, maxV;

while(1)
{
pivot = nums[m++];
while(m<=n)
{
if(nums[m]>=pivot) m++;
else if(nums[n]<pivot) n--;
else {swap(nums[m++], nums[n--]);}
}
}

}
``````

};

• This post is deleted!

• You can check. Making a heap is not that expensive

• This post is deleted!

• I think you have to change if(nums[m]>=pivot) m++; to if(nums[m]>=pivot && m<right) m++;

• This post is deleted!

• This post is deleted!

• Thanks for sharing! Inspired by your `QuickSelect` `iterative` solution. This one is a little different .

``````int findKthLargest(vector<int>& nums, int k) { //average O(n), worst case O(n2)
if(k<1 || k>nums.size()) return -1;
int start = 0, end = nums.size()-1;
int pivot, l, r;
while(1){
pivot = nums[start]; l = start; r = end; //set the pivot and checking window

while(l <= r){
if(nums[l] >= pivot) l++;
else if(nums[r] <= pivot) r--;
else {swap(nums[l], nums[r]);}
}
swap(nums[start], nums[r]); //pivot is fixed at index r, which is (r+1)th

if(k == r+1) return nums[r];
else if(k > r+1) start = r+1; //move to pivot's right part
else {end = r-1;} //move to pivot's left part
}
}``````

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