[LeetCode 75] Medium - 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:
        nums.sort()
        return nums[-k]

 

정렬 하지 않고 푸는 법

- Heap / Priority Queue 사용 

- 힙 큐, 우선순위 큐

 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for n in nums:
            heapq.heappush(heap, -n) # - 붙임으로써 큰->작은순으로 정렬

        while k:
            res = heapq.heappop(heap)
            k-=1
        return -res

 

 

참고:

https://littlefoxdiary.tistory.com/3

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기