LeetCode Top Interview 150) Kth Largest Element in an Array

Question

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?

Constraints:

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

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

---

---

정렬되지 않은 정수리스트 nums에서 k번째로 큰 수를 찾는 문제입니다.
문제의 마지막 줄에서 정령을 사용하지 않는 방법을 고려해보라고 합니다.

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = nums[:k]
        heapify(heap)
        for n in nums[k:]:
            if n > heap[0]:
                heapreplace(heap,n)
        return heap[0]

• nums의 k번째까지의 힙 구조를 heap으로 저장합니다.
• nums의 k번째부터 끝까지 탐색합니다.
  • 만약 탐색중인 숫자가 heap[0]보다 크면 heap[0] 값을 n으로 대체합니다.
    • heapreplace함수를 통해 한 번의 수행만 합니다.

---

간단해 보이지만 최적화에서 고민이 길었습니다.

처음에는 nums자체를 heapify해서 k번째 수가 나올때까지 반복문으로 heappop을 해보는 방식을 생각했지만 속도가 느려서 최적화를 거쳤습니다.

단순히 nums를 heapify하면 전체 힙 구조를 유지하게 되므로 k만큼의 사이즈만 힙구조화 하기 위해 heap 리스트를 따로 만들었습니다.

그래도 효율성이 낮게 나오길래 다른 사람 코드를 비교해보니 그냥 정렬함수 사용해서 k번째 원소 찾는게 더 빨리 나왔습니다.

아마 파이썬 내장 정렬함수인 Tim sort함수의 성능이 좋아서 그런듯합니다. 백분율이 몰려있어서 작은 차이도 큰 백분율 차로 보이게 됐지만 성능에서 큰 차이는 없었습니다.