[LeetCode] 215. Kth Largest Element in an Array

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

Kth Largest Element in an Array - LeetCode

Kth Largest Element in an Array - Medium

 

 

배열에서 k번째로 큰 수를 출력해주면 된다.

priority_queue를 가장 작은 수가 먼저 꺼내지도록 만든 뒤,

그 사이즈가 k 미만이면 채우고,

k 이상이면 top과 현재수를 비교하여 top 보다 클경우엔 pop 후 push를 반복해준다.

마지막으로 top을 리턴하면 된다.

 

전체 풀이 코드

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i=0; i<nums.size(); i++) {
            if (pq.size() < k) pq.push(nums[i]);
            else if (pq.top() < nums[i]) {
                pq.pop();
                pq.push(nums[i]);
            }
        }
        return pq.top();
    }
};