[leetcode] 215. Kth Largest Element in an Array 파이썬 코드

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

 

정수로 되어 있는 배열 nums에서 k번째로 큰 숫자를 찾는 것이다. "정렬" 알고리즘을 사용하지 않고!

 

내가 푼 방법은 heap을 사용했는데 max heap을 사용했다. 

max heap을 써서 k-1번 heappop(nums)을 해주고, 그 힙에서 0번째 값에 (-1)을 곱해서 리턴해주었다.

 

class Solution(object):
    def findKthLargest(self, nums, k):
        nums = [(-1) * i for i in nums]
        heapq.heapify(nums)
        for _ in range(k-1):
            heapq.heappop(nums)
        return nums[0] * (-1)

 

 

그런데 내 코드는 다른 사람들과 비교했을 때 효율적이지 않았다.

 

정렬의 시간 복잡도는 n * log(n) 이고, 내 코드의 시간 복잡도는 max heap을 만드는데 O(n)과 k 번 heappop 하는데 O(klogn)을 더한  O(n + klogn) 이다.