[LeetCode] 215. Kth Largest Element in an Array

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

Kth Largest Element in an Array - LeetCode

문제 유형 : 우선순위 큐

문제 난이도 : Medium

 

 

문제

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.

You must solve it in O(n) time complexity.

 

nums배열과 정수 k가 주어진다. 배열에서 k번째로 큰수를 반환해야 한다. 중복된 수 모두 각각의 요소로 인정한다.

시간복잡도 O(n)이내로 해결해야 한다.

 

 

풀이

최소 힙의 우선순위 큐를 만들어서 k개 이하일때는 요소를 넣어주면 되고, k개 이상일때부터는 새로 들어오는 수와 최소 힙의 가장 작은 수를 비교하여 새로 들어오는 수가 더 큰 경우, 우선순위 큐의 맨 위를 빼고, 새로 요소를 넣어준다.

nums의 순회가 끝나면, 우선순위 큐의 맨 위를 반환하면 K번째 큰 수가 반환될것이다.

 

코드(C++)

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(nums[i] > pq.top()){
                    pq.pop();
                    pq.push(nums[i]);
                }
            }
        }

        return pq.top();
    }
};