[알고리즘/python] LeetCode 215. Kth Largest Element in an Array

📑 1. 문제 이해

https://leetcode.com/problems/kth-largest-element-in-an-array/?envType=study-plan-v2&envId=top-interview-150 

Kth Largest Element in an Array - LeetCode

# len(nums) - k + 1 . 5개 중 2번째로 큰 값은 4번째로 작은값
# 중복된 값 있을 수 있음. [1,2,3,4,4,5]에서 k =3 이라면 4가 반환되어야함.
# k가 len(nums) 보다 큰 비정상적인 경우는 입력으로 주어지지 않음
# nums는 빈 배열일 수 없음
# without sort. sorting하면 가장 최적화되어있기 때문에 빠름. tim sort c로 구현되어 있기 때문에 매우 빠르다.

☑️ 테스트케이스

문제에서 주어진 테스트 케이스를 분석해보면 다음과 같습니다. 

 

Example1: 

 

추가로 살펴봐야할 테스트 케이스는 다음과 같습니다.

 

 

💡 2. 알고리즘 설계

 python은 최소힙만 제공하니깐 값을 반전시켜서 최대힙으로 만들든가

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        q = []
        for a in nums:
            if len(q) < k:
                heapq.heappush(q, a)
            else:
                if a > q[0]:
                    heapq.heappushpop(q, a)
        return heapq.heappop(q)

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N)

공간 복잡도: O(N)

  def findKthLargest2(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        for _ in range(len(nums) - k):
            heapq.heappop(nums)
        return heapq.heappop(nums)

 

⚒️ 3. 최적화

    def findKthLargest(self, nums: List[int], k: int) -> int:
        q = []
        for a in nums:
            if len(q) < k:
                heapq.heappush(q, a)
            else:
                if a > q[0]:
                    heapq.heappushpop(q, a)
        return heapq.heappop(q)

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N)

공간 복잡도: O(N)

 ⎌ 4. 검토

---

✅ 정리

◎ 정리1