Heap-PrioiryQueue: 215. Kth Largest Element in an Array ★

215. Kth Largest Element in an Array

 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # minheap 으로 만들고, k개 까지. 힙 개수 유지하게 하면, 
        # k 개 보다 많으면 작은 것들 제거
        # 그렇게 하면, minheap[0]에는 k번째 큰 것이 남아있음

        heapq.heapify(nums)

        while( len(nums) > k):
            heapq.heappop(nums)

        return nums[0]

 

메모리 절약을 위해,

k 개 만큼 우선 넣어서, minheap 만들고.

1개씩 추가해서, k개 넘는 것은 삭제하는 식으로..

 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Create a min heap with the first k elements of the array
        # 배열의 처음 k개의 요소로 최소 힙 생성
        minheap = nums[:k]
        heapq.heapify(minheap)  # Transform the list into a valid min heap
                               # 리스트를 최소 힙으로 변환

        # Iterate through the rest of the elements in the array
        # 배열의 나머지 요소를 순회
        for num in nums[k:]:
            heapq.heappush(minheap, num)  # Add the current number to the heap
                                          # 현재 숫자를 힙에 추가
            heapq.heappop(minheap)        # Remove the smallest number to maintain size k
                                          # 힙의 크기를 k로 유지하기 위해 가장 작은 값을 제거

        # The root of the min heap is the kth largest element
        # 최소 힙의 루트 노드가 k번째로 큰 값
        return minheap[0]  # Return the kth largest element
                           # k번째로 큰 값을 반환