forked from mdmzfzl/NeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0215-kth-largest-element-in-an-array.rs
47 lines (39 loc) · 1.62 KB
/
0215-kth-largest-element-in-an-array.rs
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
Problem: LeetCode 215 - Kth Largest Element in an Array
Key Idea:
The key idea is to use a min-heap (priority queue) to efficiently find the kth largest element in the array.
Approach:
1. Create a min-heap (priority queue) with a capacity of k elements.
2. Iterate through the array:
- Insert each element into the min-heap.
- If the min-heap size exceeds k, remove the smallest element (pop from the heap).
3. The top element of the min-heap (the root) will be the kth largest element.
Time Complexity:
- Heap Insertion and Extraction: O(log k) per operation, where k is the value of 'k'.
- We perform this operation for each of the 'n' elements in the array.
- Overall time complexity is O(n log k).
Space Complexity:
O(k), as the min-heap can contain at most k elements.
*/
use std::cmp::Reverse;
use std::collections::BinaryHeap;
impl Solution {
pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {
// Create a min-heap with a capacity of k
let mut min_heap: BinaryHeap<Reverse<i32>> = nums
.iter()
.take(k as usize)
.map(|&num| Reverse(num))
.collect();
// Iterate through the remaining elements
for &num in nums.iter().skip(k as usize) {
// If the current number is larger than the smallest number in the min-heap, replace it
if num > min_heap.peek().unwrap().0 {
min_heap.pop();
min_heap.push(Reverse(num));
}
}
// The top of the min-heap contains the kth largest element
min_heap.peek().unwrap().0
}
}