엔지니어 게시판
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 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.

 

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 to add.
  • It is guaranteed that there will be at least k elements in the array when you search for the kth 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



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.

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];
    }
};
전체 29 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0