Challenge 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.
Example:
Input: [3,2,3,1,2,4,5,5,6] and k = 4Output: 4
Approach #1: Sort the array and get by index
Time complexity is O(NlogN), a flaw is we modified the original array.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
Approach #2: Use heak minheap with size K
If we initialize a minheap with the size of K, the top value is what we want.
For minheap, the insertion operation has a worst-case time complexity of O(logN) but an average-case complexity of O(1).
So we have an overall average-case complexity of O(N) and worst time complexity O(NlogN).
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minheap;
for(int i=0; i<k; i++)
minheap.push(nums[i]);
for(int i=k; i<nums.size(); i++){
if(nums[i] <= minheap.top()) continue;
minheap.pop();
minheap.push(nums[i]);
}
return minheap.top();
}
};
Approach #3: Divide and conquer
Just like quicksort, we use a partition
function to split the array into two parts, the left part of elements are all less than pivot
, the right part of elements are all greater than pivot
.
And reduce the search range in every iteration.
The overall time complexity O(N).
class Solution {
private:
void swap(vector<int>& a, int x, int y) {
int t = a[y];
a[y] = a[x];
a[x] = t;
}
int random(int a, int b) {
return (int) (rand() % (b - a + 1)) + a;
}
int partition(vector<int>& nums, int left, int right, int index) {
int pivot = nums[index];
swap(nums, index, right);
int i = left - 1;
for (int j=left; j<=right-1; j++)
if (nums[j] <= pivot)
swap(nums, ++i, j);
swap(nums, right, i+1);
return i+1;
}
int quick_select(vector<int>& nums, int left, int right, int k) {
while (left <= right) {
int pivot = partition(nums, left, right, random(left, right));
if (pivot == k) return nums[k];
else if (k > pivot) left = pivot + 1;
else right = pivot - 1;
}
return -1;
}
public:
int findKthLargest(vector<int>& nums, int k) {
return quick_select(nums, 0, nums.size() - 1, nums.size() - k);
}
};
The post Kth Largest Element in an Array appeared first on Coder's Cat.
Top comments (0)