[LEET CODE] 215. Kth Largest Element in an Array

# Problem

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.     Constraints: 1 <= k <= nums.length <= 104 -104 <= nums[i] <= 104

k 번째로 큰 수 구하기 

 

# My Answer - 정렬 이용 (solution 4)

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

 

# Solution 1 - heap 모듈 이용

import heapq

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

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

        return -heapq.heappop(heap)

heapq 는 최소힙으로 구현되어 있으므로 음수로 저장해 최대힙으로 구현

 

# Solution 2 - heap 모듈의 heapify 이용

import 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)

heapify - 주어진 자료구조가 힙 특성을 만족하도록 바꿔주는 연산

 

# Solution 3 - heap 모듈의 nlargest 이용

import heapq

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

nlargest - n개의 큰 값 순서대로 추출

인덱스 -1로 n번째 큰 값 추출

 

# Solution 4 - 정렬을 이용한 풀이

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

---

# 힙 ( heap )

최소힙 - 부모가 항상 자식보다 작거나 같다 ( 좌우 트리는 정렬된 구조는 아님)

최대힙 - 부모가 항상 자식보다 크거나 같다

거의 완전한 트리인 특수한 트리 기반 자료구조

우선순위 큐 구현