LeetCode 215. Kth Largest Element in an Array

파이썬 알고리즘 인터뷰 55번(리트코드 215) Kth Largest Element in an Array
https://leetcode.com/problems/kth-largest-element-in-an-array/

나의 풀이1

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, (-num, num))
        for _ in range(k - 1):
            heapq.heappop(heap)
        return heapq.heappop(heap)[1]

나의 풀이2

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[-k]

다른 풀이1

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, -num)
        for _ in range(1, k):
            heapq.heappop(heap)
        return -heapq.heappop(heap)

다른 풀이2

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        
        for _ in range(len(nums) - k):
            heapq.heappop(nums)

        return heapq.heappop(nums)

다른 풀이3

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]

배운 점

• heapq.heapify(list)는 새로운 list를 생성하지 않고 원래 list를 수정한다.
• heapq.nlargest등 heapq 의 여러 메서드에 대한 자세한 글

힙(Heap)과 우선순위 큐(Priority Queue)에 대한 글
https://velog.io/@coding_study/힙Heap과-우선순위-큐Priority-Queue