•
문제 설명 : 제공된 배열 중, K번째로 큰 값을 반환
•
풀이 방법
◦
간단하게는 정렬된 인덱스를 구하는 방법이 있다.
◦
문제에서는 sorting을 사용하지 않는 방법도 사용해보길 권장해서, heap을 사용하였다.
•
시간복잡도 :
•
성공 코드
파이썬의 heapq는 최소힙만 사용 가능하다.
최대힙으로 사용하기 위해서는, 추가되는 값을 음수로 변경하여 넣으면 절대 값이 큰 값들이 가장 작은 값으로 설정 될 것이다.
import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = []
for num in nums:
heapq.heappush(heap, num * -1)
for _ in range(k - 1):
heapq.heappop(heap)
return heapq.heappop(heap) * -1
Python
복사