[Leetcode 215] - Kth Largest Element in an Array w/ Python

 

 

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Can you solve it without sorting?

 

 

 

숫자가 들어가 있는 배열과 정수 k가 주어졌을때 정렬 없이

배열에서 k번째로 큰 숫자를 리턴하는 문제

 

 

 

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

 

 

 

---

 

 

 

Example 1:

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

 

 

 

Example 2:

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

 

 

 

---

 

 

 

heapq를 통해 정렬을 하고 전체 길이에서 k를 뺀만큼

heap에서 제거하면 된다

 

이를 통해 정렬 없이 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)