[LeetCode] 215. Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/description

Algorithm

quick select에 대해 배운 문제! 단순정렬해 풀면 복잡도가 nlogn이지만 이문제는 더 효율적으로 풀길 요구한다.나는 maxHeap으로 풀었는데, 평균적경우 더 효율적일수 있는 풀이가 있어 기록을 남긴다. 먼저 나의 처음 나의 풀이는 다음과 같다.k largest문제이니 minHeap으로 k번째초과면 pop() 하는 방식으로 풀 수도 있을것 같다.

 

 

이정도면 됐지,싶었다 ㅋ근데 퀵을 활용한 다른 풀이가있다..?!

바로 quick select 방법을 이용하면 평균적으로 O(n) 만에 k 번째를 찾을 수 있다! (n + n/2 + n/4...)

• pivot을 설정한다.(여기선 맨오른쪽으로 설정)
• p 포인터를 옮겨나가며, 마지막에 도달하면 pivot과 p를 스왑한다.
• len(배열) - k 는 정렬되었을때 k번째로 큰 배열인덱스이다. k가 p보다 크다면, p 기준 오른쪽파티션에 대해 탐색하고 아니면 그반대로 탐색하며 범위를 좁혀나간다.

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

        def quickSelect(l, r):
            pivot, p = nums[r], l
            for i in range(l, r):
                if nums[i] <= pivot:
                    nums[p], nums[i] = nums[i], nums[p]
                    p+=1
            nums[p], nums[r] = nums[r], nums[p]

            if p > k: return quickSelect(l, p - 1)
            elif p < k: return quickSelect(p + 1, r)
            else:       return nums[p]
        
        return quickSelect(0, len(nums) - 1)

근데 위의경우, 40/41 테스트케이스에서 에러가 난다 ㅋ 왜냐...바로 최악의 경우(pivot이 항상 제일 큰 값일때) 엔 O(n^2) 시간복잡도를 가지기 때문이다. 하지만 이 최악의 경우가 자주 나오진않으므로...뭐 효율적인 풀이중 하나라고 볼순 있을것같다.

 

그래서 내 생각에는 늘 최악의 경우를 우선 고려해야하므로, 내 풀이처럼 Heap을 사용해푸는게 좋은듯! bb 아래 파이썬,자바 풀이 로직이 살짝 다르게 풀었다!

---

Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        maxHeap = [[-n,n] for n in nums]
        heapq.heapify(maxHeap)
        ans = [0,0]
        while k > 0:
            ans = heapq.heappop(maxHeap)
            k-=1
        return ans[1]

 

이 코드의 시간 복잡도는 O(n + klogn)이다. 여기서 n은 heapify(), k는 pop 횟수, logn은 힙큐에서 pop() 시간 복잡도이다.

 

Java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        return minHeap.peek();
    }
}

 

힙 사이즈가 k이고, 넣고 뺄 때는 logk인데 그걸 모든 원소 n개에 대해 반복하니까 이 코드의 시간 복잡도는 O(nlogk)이다.