[코테] 리트코드 힙 215. Kth Largest Element in an Array

215. Kth Largest Element in an Array

문제 링크

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

문제 설명

Given an integer array nums and an integer k, return the k^th largest element in the array.

Note that it is the k^th largest element in the sorted order, not the k^th distinct element.

Can you solve it without sorting?

제한 사항

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

입출력 예 #1

1. Input : nums = [3,2,1,5,6,4], k = 2
2. Output : 5

입출력 예 #2

1. Input : nums = [3,2,3,1,2,4,5,5,6], k = 4
2. Output : 4

문제 풀이

1. heapq 모듈을 이용한 풀이
2. heapq 모듈 내 heapify 이용한 풀이
3. heapq 모듈 내 nlargest 이용한 풀이
4. 정렬을 이용한 풀이

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

        for _ in range(k-1):
            heapq.heappop(heap)

        return -heapq.heappop(heap)

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)

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

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums, reverse=True)[k-1]