LeetCode 솔루션

703. Kth Largest Element in a Stream

Jack 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.04.09 17:43

9,328 조회
3 댓글
0 추천
0 비추천
목록 게시글 쓰기

[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.

#Leetcode, #문제 풀이, #시즌3, #Easy, #Amazon, #Facebook, #Tree, #Design, #Binary Search Tree, #Heap, #Priority Queue, #Binary Tree, #Data Stream

링크

https://leetcode.com/problems/kth-largest-element-in-a-stream/ 3439 회 연결

익명
작성일 2022.04.10 09:26

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]

익명
작성일 2022.04.10 13:26

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();
    }
};

익명
작성일 2022.04.11 22:13

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];
    }
};