215. Kth Largest Element in an Array
1. Description
Given an integer array nums and an integer k, return the $k^{th}$ largest element in the array.
Note that it is the $k^{th}$ largest element in the sorted order, not the $k^{th}$ distinct element.
You must solve it in O(n) time complexity.
2. Example
Example 1
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
3. Constraints
- 1 <= k <= nums.length <= $10^5$
- $-10^4$ <= nums[i] <= $10^4$
4. Solutions
Heap
n = nums.size()
Time complexity(): O(nlogk)
Space complexity(): O(k)
class Solution {
public:
int findKthLargest(const vector<int> &nums, int k) {
priority_queue<int, vector<int>, greater<int>> max_k_values;
for (const int num : nums) {
max_k_values.push(num);
if (max_k_values.size() > k) {
max_k_values.pop();
}
}
return max_k_values.top();
}
};
Quickselect (Lomuto, i.e., single pointer)
n = nums.size()
Time complexity(): O(n)
Space complexity(): O(logn)
class Solution {
public:
int findKthLargest(vector<int> nums, int k) {
partition(nums, 0, nums.size(), k);
return nums[k - 1];
}
private:
void partition(vector<int> &nums, int left, int right, int k) {
int pivot_index = (left + right) / 2, pivot_value = nums[pivot_index];
swap(nums[left], nums[pivot_index]);
int index = left;
for (int i = left + 1; i < right; ++i) {
if (nums[i] > pivot_value) {
++index;
swap(nums[i], nums[index]);
}
}
swap(nums[left], nums[index]);
if (index < k - 1) {
partition(nums, index + 1, right, k);
} else if (index > k - 1) {
partition(nums, left, index, k);
}
}
};