[leetcode 2024/02/08] 215. Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

이번 문제는 nums array에서 k 번째로 큰 array를 출력하는 것이 목표이다.

그냥 sort하고, index [k-1] 을 이용해서 출력하면 간단하지만, "Can you solve it without sorting?" 이라고 했기에, heap으로 문제를 풀어볼 것이다.

 

우선 python의 경우 min heap 만 지원하기 때문에, list에 -1을 곱해주고, heapify를 해주어서 정렬하였다.

nums = [-1*i for i in nums]
heapq.heapify(nums)

 

이렇게 한다면,

[3, 2, 1, 5, 6, 4] -> [-6, -5, -4, -3, -,2, -1] 로 정렬될 것이다.

 이후, k 개를 pop 한 후, 나온 결과에 -1을 곱해서 return 할 것이다.

 

즉, k가 2라면 -5 * -1 을 return -> 5 를 return 할 것이다.

 

2. 코드

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums = [-1*i for i in nums]
        heapq.heapify(nums)

        for i in range(k):
            result = heapq.heappop(nums)

        return -1*result