LeetCode 솔루션 분류
703. Kth Largest Element in a Stream
본문
[Leetcode 시즌 3] 2022년 4월 8일 문제입니다
[Easy] 703. Kth Largest Element in a Stream
Design a class to find the kth
largest element in a stream. Note that it is the kth
largest element in the sorted order, not the kth
distinct element.
Implement KthLargest
class:
KthLargest(int k, int[] nums)
Initializes the object with the integerk
and the stream of integersnums
.int add(int val)
Appends the integerval
to the stream and returns the element representing thekth
largest element in the stream.
Example 1:
Input ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output [null, 4, 5, 5, 8, 8] Explanation KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8
Constraints:
1 <= k <= 104
0 <= nums.length <= 104
-104 <= nums[i] <= 104
-104 <= val <= 104
- At most
104
calls will be made toadd
. - It is guaranteed that there will be at least
k
elements in the array when you search for thekth
element.
관련자료
-
링크
댓글 3
coderoncruise님의 댓글
- 익명
- 작성일
Python
1. Not distinct element => consider duplicate numbers e.g. [1,2,2,3]
2. Brute force: Add O(n) + Sort O(nlogn)
3. Min heap of Size K: Add/Pop Log K
1. Not distinct element => consider duplicate numbers e.g. [1,2,2,3]
2. Brute force: Add O(n) + Sort O(nlogn)
3. Min heap of Size K: Add/Pop Log K
import heapq
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.pq = [float('-inf')] * k
for n in nums:
if n > self.pq[0]:
heapq.heapreplace(self.pq,n)
def add(self, val: int) -> int:
if val > self.pq[0]:
heapq.heapreplace(self.pq,val)
return self.pq[0]
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 68 ms, faster than 19.99% of C++ online submissions for Kth Largest Element in a Stream.
Memory Usage: 22.2 MB, less than 5.49% of C++ online submissions for Kth Largest Element in a Stream.
Runtime: 68 ms, faster than 19.99% of C++ online submissions for Kth Largest Element in a Stream.
Memory Usage: 22.2 MB, less than 5.49% of C++ online submissions for Kth Largest Element in a Stream.
class KthLargest {
private:
multiset<int> s;
int k;
public:
KthLargest(int k, vector<int>& nums) {
this->s = multiset<int>(nums.begin(), nums.end());
this->k = k;
while (this->s.size() > this->k) {
this->s.erase(s.begin());
}
}
int add(int val) {
this->s.insert(val);
if (this->s.size() > k) {
this->s.erase(s.begin());
}
return *this->s.begin();
}
};
bobkim님의 댓글
- 익명
- 작성일
class KthLargest {
public:
int K;
std::vector<int> vec;
KthLargest(int k, vector<int>& nums) {
vec=nums;
K=k;
sort(vec.begin(),vec.end(),greater<int>());
}
int add(int val) {
if(vec.empty()){
vec.push_back(val);
}else{
if(vec.back()>=val){
vec.push_back(val);
}else{
for(std::vector<int>::iterator itr=vec.begin();itr!=vec.end();itr++){
if(val>=*itr){
vec.insert(itr,val);
break;
};
};
};
};
return vec[K-1];
}
};