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
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);
}
}
};