Kth Largest Element In An Array

Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

test

Solutions

There are five different solutions in this including partition, recursion, max heap, selection sort and just sorting.

Partition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int findKthLargest(vector<int>& nums, int k) {
int size = nums.size();
int left=0, right=size-1;
srand((unsigned(time(NULL))));
for(int i = 0; i < size; ++i)
swap(nums[i], nums[rand()%size]);
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;
}

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
int findKthLargest(vector<int>& nums, int k) {
int small = INT_MAX, big = INT_MIN;
vector<int> smaller, bigger;
for(int i = 0; i < nums.size(); ++i)
small = min(small, nums[i]), big = max(big, nums[i]);
if(small == big) return big;
int m = small+((big-small)>>1);
for(int i = 0; i < nums.size(); ++i)
nums[i]>m? bigger.push_back(nums[i]):smaller.push_back(nums[i]);
if(bigger.size() >= k) return findKthLargest(bigger, k);
else return findKthLargest(smaller, k-bigger.size());
}

Maxheap

1
2
3
4
5
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

1
2
3
4
5
6
7
8
9
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];
}

Sorting

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

Built-in method

1
2
3
4
int findKthLargest(vector<int>& nums, int k) {
nth_element(nums.begin(), nums.begin()+nums.size()-k, nums.end());
return nums[nums.size()-k];
}

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