# Two ways: Heap based solution and modified quicksort

• specialized quick sort

``````int findKthLargest(vector<int>& nums, int k) {
int l=0, r=nums.size(), i, j, idx;
while( l < r ) {
idx = (l + r)/2;
swap( nums[idx], nums[r-1] );
i = l; j = l;
while( i < r-1 ) {
if( nums[i] >= nums[r-1] ) swap(nums[i++], nums[j++]);
else i++;
}
swap(nums[r-1], nums[j++]);
if( j-l > k ) r = j-1;
else if( j-l == k ) return nums[j-1];
else {
k -= (j-l);
l = j;
}
}
return nums[l+k-1];
}
``````

heap solution

``````class Solution {
private:
void createHeap(vector<int>& heap) {
for( int i=heap.size()/2; i>=0; i-- ) {
heapify(heap, i);
}
}
void heapify(vector<int>& heap, int i) {
if( i < heap.size() ) {
int idx = i, val = heap[i];
if( 2*i+1 < heap.size() && heap[2*i+1] < val ){
idx = 2*i + 1;
val = heap[2*i+1];
}
if( 2*i+2 < heap.size() && heap[2*i+2] < val ) {
idx = 2*i + 2;
val = heap[2*i+2];
}
if( idx != i ) {
swap( heap[idx], heap[i] );
heapify(heap, idx);
}
}
}
public:
int findKthLargest(vector<int>& nums, int k) {
vector<int> heap(nums.begin(), nums.begin() + k);
createHeap(heap);
for( int i=k; i<nums.size(); i++) {
if( nums[i] <= heap[0]) continue;
heap[0] = nums[i];
heapify( heap, 0 );
}
return heap.front();
}
};``````

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