A summary: maxHeap, selectionSort, sorting, recursion and partition methods

• partition

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

int partition(vector<int>& nums, int left, int right)
{
int pivot=nums[left];
int l=left+1, r=right;
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--;
}
swap(nums[left], nums[r]);
return r;
}
``````

recursive

``````int findKthLargest(vector<int>& nums, int k)
{
int n = nums.size();
if (n==1) return nums[0];
int big = nums[0], small = big;
vector<int> left;
vector<int> right;
for (int i = 1; i < n; i++)
{
if (nums[i] > big) big = nums[i];
if (nums[i] < small) small = nums[i];
}
const double mid = (big + small) / 2.0; //make the partition more even
for (int i = 0; i < n; i++)
{
if (nums[i] <= mid) left.push_back(nums[i]);
else right.push_back(nums[i]);
}
if (left.size() == n) return nums[0]; //all elements are the same
if (left.size() >= n-k+1)
return findKthLargest(left, k-right.size());
else
return findKthLargest(right, k);
}
``````

max heap using priority_queue

``````int findKthLargest(vector<int>& nums, int k)
{
priority_queue<int, vector<int>, less<int>> maxHeap(nums.begin(), nums.end());
for(int i = 1; i < k; ++i) maxHeap.pop();
return maxHeap.top();
}
``````

selection

``````int findKthLargest(vector<int>& nums, int k)
{
for(int i = 0; i < k; i++)
{
int localMax = i;
for(int j = i+1; j < nums.size(); ++j)
if(nums[j] > nums[localMax]) localMax = j;
swap(nums[i], nums[localMax]);
}
return nums[k-1];
}
``````

sort

``````int findKthLargest(vector<int>& nums, int k)
{
sort(nums.begin(), nums.end(), greater<int>());
return nums[k-1];
}
``````

Always welcom new ideas and practical tricks, just leave them in the comments!

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