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
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) {
srand(time(nullptr));
int random_index = rand() % (right - left) + left;
int base_number = nums[random_index];
swap(nums[left], nums[random_index]);
int index = left;
for (int i = left + 1; i < right; ++i) {
if (nums[i] > base_number) {
swap(nums[i], nums[index + 1]);
++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);
}
}
};