[알고리즘] Kth Largest Element in an Array

포인트

1. 파이썬이 다시 한번 대단함을 느낀다

 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end()); //min heap
        //priority_queue<int, vector<int>, greater<int>()> max heap
        
        for (int i = 0; i < k - 1; i++) {
            pq.pop();
        }
        return pq.top();
    }
};

먼저 cpp는 우선 순위 큐를 활용하여 heap sort 를 진행을 하였다. 

최선, 최악, 평균이 전부 시간 복잡도 O(nlogn)을 차지한다. 

 

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

파이썬은 코드가 정말 간단하다. 

print를 제외하고 정렬뒤 -k로 접근을 해준다.