Kth Largest Element in a Stream[E,Tree,Design,Binary Search Tree,Heap (Priority Queue),Binary Tree,Data Stream]

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

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.

난이도 easy인데 어렵다. 기본 skeleton code도 struct를 만드는거부터 시작이 되던데..

C로 struct type 설계하는 게 쉽지가 않다.

 

1. C

Heap을 이용한 느낌이다. 뭔가 시험에 나올법한 문제긴 하다.

#include <stdio.h>
#include <stdlib.h>

// KthLargest 구조체 정의
typedef struct {
    int k;          // k번째 큰 요소를 추적하기 위한 변수
    int* elements;  // k개의 요소를 저장할 배열 포인터
    int size;       // 현재 배열에 저장된 요소의 개수
} KthLargest;

// KthLargest 구조체를 초기화하는 함수
KthLargest* kthLargestCreate(int k, int* nums, int numsSize) {
    // 메모리 할당 및 k와 size 초기화
    KthLargest* obj = (KthLargest*)malloc(sizeof(KthLargest));
    obj->k = k;
    obj->size = 0;
    obj->elements = (int*)malloc(k * sizeof(int));  // k 크기의 배열 할당

    // 초기 nums 배열의 요소들을 k개의 큰 값으로 유지하도록 배열에 저장
    for (int i = 0; i < numsSize; i++) {
        if (obj->size < k) {
            // 배열에 공간이 남아 있다면 그냥 삽입
            obj->elements[obj->size++] = nums[i];
        } else {
            // 배열에 공간이 없는 경우, 현재 배열의 가장 작은 값을 찾아서 교체
            int minIndex = 0;
            for (int j = 1; j < obj->size; j++) {
                if (obj->elements[j] < obj->elements[minIndex]) {
                    minIndex = j;
                }
            }
            if (nums[i] > obj->elements[minIndex]) {
                obj->elements[minIndex] = nums[i];
            }
        }
    }
    return obj;
}
int kthLargestAdd(KthLargest* obj, int val) {
    if (obj->size < obj->k) {
        // 아직 배열에 공간이 남아 있으면 값을 삽입
        obj->elements[obj->size++] = val;
    } else {
        // 배열이 꽉 찬 경우, 현재 배열에서 가장 작은 값을 찾아서 새 값으로 교체
        int minIndex = 0;
        for (int i = 1; i < obj->size; i++) {
            if (obj->elements[i] < obj->elements[minIndex]) {
                minIndex = i;
            }
        }
        if (val > obj->elements[minIndex]) {
            obj->elements[minIndex] = val;
        }
    }
    // 현재 배열에서 가장 작은 값을 찾아서 반환 (k번째 큰 값이 됨)
    int min = obj->elements[0];
    for (int i = 1; i < obj->size; i++) {
        if (obj->elements[i] < min) {
            min = obj->elements[i];
        }
    }
    return min;

}

void kthLargestFree(KthLargest* obj) {
    free(obj->elements);
    free(obj);
}

/**
 * Your KthLargest struct will be instantiated and called as such:
 * KthLargest* obj = kthLargestCreate(k, nums, numsSize);
 * int param_1 = kthLargestAdd(obj, val);
 
 * kthLargestFree(obj);
*/

 

2. C++

minheap 이용하면 편하다.

class KthLargest {
public:
    int k;
    priority_queue<int,vector<int>,greater<int>> pq;
    KthLargest(int k, vector<int>& nums):k(k){
        for(int x:nums){
            pq.push(x);
            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);
 */

 

 

3. Python

파이썬방법1 - > 간편식

# Python 간편식
class KthLargest:

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

    def add(self, val: int) -> int:
        lst = []
        self.nums.append(val)
        self.nums.sort()
        return self.nums[-self.k]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

방법 2 -> heapq 사용

import heapq
# Python heap 이용
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.min_heap = []
        
        for num in nums:
            self.add(num)

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


# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)