[DSA][Heap] 04. Kth Largest Element in an Array

LeetCode 215

 

04. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?

 

[질문하기]

- nums 배열의 길이는 항상 k 이상인가요? YES

 

 

[풀이 1] Min Heap

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        elem = 0
        k = len(nums) - k + 1
        while k > 0:
            elem = heapq.heappop(nums)
            k -= 1
        return elem

앞서 나왔던 Heap 문제들과 크게 다르지 않다. heapify로 heap 구조를 만들어준 후, Max Heap으로 저장하면 k번째를, Min Heap으로 저장하면 len(nums) - k + 1 번째 원소를 return 해주면 된다. heappop 연산을 k만큼 반복하므로 klogn의 시간 복잡도를 가지지만, 크기가 k인 min-heap을 유지하면서 배열을 순회하면 시간 복잡도를 nlogk로 줄일 수 있다.

 

 

⏱️ 시간복잡도

길이 n짜리 heap에 pop 작업을 반복해야 하므로, O(logn) 연산을 k번 반복하게 된다. 따라서 전체 시간 복잡도는 O(klogn)이다.

🧠 공간복잡도

In-place로 수행되기 때문에, 공간 복잡도는 O(1)이다.