[LeetCode] 703. Kth Largest Element in a Stream

https://leetcode.com/problems/kth-largest-element-in-a-stream/description/?envType=daily-question&envId=2024-08-12

leetcode = Kth Largest Element in a Stream

문제 유형 : 우선순위 큐

문제 난이도 : Easy

 

문제

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 integer k and the stream of integers nums.
• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

 

스트림에서 k번째로 큰 숫자를 찾는 클래스를 디자인하라.

중복포함 순위가 매겨져서 k번째임에 유의하라.

 

KthLargest(int k, int[] nums)는 정수 k를 정의하고, 초기 스트림 nums를 설정합니다.

int add(int val)은 정수 val을 스트림에 넣고 k번째로 큰 요소를 반환합니다.

 

풀이

최소 힙을 하나 만들어서, 저장시킬 것이다.

 

KthLargest는 다음과 같이 구현하자:

k를 멤버 함수로 설정하고, 우선순위 큐에 nums의 요소들을 각각 넣는다.

만약 우선순위 큐에 있는 요소의 개수가 k개를 넘어가면, 우선순위 큐에서 요소를 제거한다.

그래서, 최소 힙에 top K개의 요소들만 가지고 있는 것이다.

 

add()는 우선순위 큐에 val을 넣고, 만약 요소의 개수가 k보다 커졌다면, 요소를 뺀다.

최소 힙에는 top K개의 요소만 남아있고, top에는 k번째로 큰 수가 존재하는 것이다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class KthLargest {
private:
    int k;
    priority_queue<int, vector<int>, greater<int>> pq;
public:
    KthLargest(int k, vector<int>& nums) {
        this -> k = k;
        for(int element : nums) {
            pq.push(element);
            if(pq.size() > k) pq.pop();
        }
    }
    
    int add(int val) {
        pq.push(val);
        if(pq.size() > k) pq.pop();
        return pq.top();
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */