215. Kth Largest Element in an Array
Description
Difficulty: Medium
Related Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
Example 1:
1
2
| Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
|
Example 2:
1
2
| Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
|
Constraints:
- 1 <= k <= nums.length <= 105
- -104 <= nums[i] <= 104
Hints/Notes
- 2023/08/27
- Priority queue
- Quick select
- No solution from 0x3F
Solution
Language: C++
Quick select
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
26
27
| class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return find(nums, nums.size() - k + 1);
}
int find(vector<int>& nums, int k) {
int pivot = nums[rand() % nums.size()];
vector<int> left, mid, right;
for (int num : nums) {
if (num < pivot) {
left.push_back(num);
} else if (num > pivot) {
right.push_back(num);
} else {
mid.push_back(num);
}
}
if (left.size() >= k) {
return find(left, k);
}
if (left.size() + mid.size() < k) {
return find(right, k - left.size() - mid.size());
}
return pivot;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int num : nums) {
pq.push(num);
if (pq.size() > k) {
pq.pop();
}
}
return pq.top();
}
};
|