[Leetcode/파이썬] 215. Kth Largest Element in an Array

Kth Largest Element in an Array

---

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?

 

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

 

Constraints:

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

 

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

이건 파이썬 리스트와 정렬을 공부했다면 쉽게 해결할 수 있을 것이다. 내림차순으로 정렬하면 K번째 큰 수를 반환하면 풀리는 문제이다. nums.length 가 10만 이기 때문에 $N^{2}$ 를 아슬아슬하게 통과할 것 같다. 내가 알기로 sort 메소드는 $(O(log N)$ 으로 동작하기 때문에 무리없이 통과할 것이라 생각한다. 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []

        for num in nums :
            heapq.heappush(heap, -num)

        for i in range(k) :
            res = heapq.heappop(heap)

        return -res

방금 마지막 문장을 읽었다. Binary Search, Two Pointer, Heap 중 정렬을 할 수 있는 혹은 되어 있는 리스트를 이용하는 알고리즘은 Binary Search, Two Pointer 이고, 정렬이 되어 있지 않은 리스트를 이용하는 문제는 Heap 을 이용할 수 있을 것이다. Heap 자체가 정렬이 되면서 삽입, 팝이 되는 기능을 이용하는 것이다. 이 문제는 정렬 없이 풀 수 있니? 라는 말이 있으니까 정렬 없이 푸는 것이고, 이 문장을 힌트로 정렬을 알아서 해주는 heap을 이용하자.

파이썬에서 힙은 기본적으로 최소 힙(min heap)이다. 삽입하면 오름차순으로 삽입되고 팝 할 때 작은 숫자를 먼저 팝 하게 된다. 이 특성을 활용하여 K 번째 수를 리턴하는 문제니까, 이를 이용하여 heappush와 heappop을 반복문으로 통하여 이용하자.

이때, 아까 말했다시피, 최소 힙이 기본이므로 이 특성을 활용하여 음수로 입력을 하게 되면 절대값이 큰 숫자가 음수로 바뀌면 작은 수로 바뀌면서 꺼내올 때 가장 먼저 나오게 된다. 음수로 집어 넣고, K번 팝을 시키면 마지막에 팝 된 수가 음수의 내가 원하는 수이다. 그럼 return 할 때 다시 -를 곱하면 원래 수로 돌아오게 된다. (이는 원래의 수가 음수여도 상관 없다.)