리트코드 215번 Kth Largest Element in an Array (Python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Solution

내 풀이

from typing import List
import heapq

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

새로운 heap 만드는데 현재 수의 -1을 곱하여 역순으로 정렬되도록 하였다.

다른 풀이

from typing import List
import heapq

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)

heapify를 이용하면 새로 할당하지 않고 구할 수 있다.

Reference

파이썬 알고리즘 인터뷰 55번