[Leetcode 703] - Kth Largest Element in a Stream w/ Python

 

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:

1. KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.

2. int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

 

 

 

스트림에서 k번째 큰 숫자를 찾는 클래스를 구현하는 문제

1. KthLargest(int k, int[] nums): k와 nums의 배열을 통해 초기 설정

2. int add(int val): val이라는 숫자를 스트림에 추가 - 매번 k번째로 큰 숫자를 리턴

 

 

 

 

https://leetcode.com/problems/kth-largest-element-in-a-stream/description/

 

 

 

---

 

 

 

 

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

 

 

 

 

 

 

---

 

 

 

 

heapq를 통해 먼저 들어오는 숫자의 순서를 파악하고,

새로운 숫자가 들어온다면 언제나 제일 큰 3개의 숫자만

남기는 형식으로 만들었다

 

이를 통해 불필요한 메모리를 줄이고 즉각적으로

3번째로 큰 숫자를 파악하는데 편리하다

 

 

import heapq

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.arr = nums
        heapq.heapify(self.arr)
        self.k = k

        while len(self.arr) > k:
            heapq.heappop(self.arr)
        

    def add(self, val: int) -> int:
        heapq.heappush(self.arr, val)
        if len(self.arr) > self.k:
            heapq.heappop(self.arr)
        return self.arr[0]