[LeetCode] 215. Kth Largest Element in an Array - Java

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

Kth Largest Element in an Array - LeetCode

---

문제

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.

Can you solve it without sorting?

 

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

 

Constraints:

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

---

풀이

풀이 과정

정수 배열 nums와 정수 k가 주어질 때 nums배열안에서 k번째로 큰 요소를 찾아 return하는 문제이다.
nums에는 중복된 요소가 존재할 수 있으며 정렬을 사용하지 않고 풀이하는 것이 이 문제의 과제이다.

해당 조건으로 문제를 풀이하기 위하여 우선순위큐를 사용한다.

PriorityQueue<Integer> pq = new PriorityQueue<>();

배열의 요소를 처음부터 탐색하며 우선순위큐에 넣어주고 만약 우선순위 큐의 사이즈가 k보다 커지게 된다면 우선순위큐의 요소를 하나 제거한다. 그러면 우선순위큐에는 우선순위가 가장 높은 수(= 제일 작은 수)가 제거되므로 최종적으로 우선순위 큐에는 가장 큰 수부터 k번째 큰 수 까지만 남게된다.

for(int i : nums) {
    // num배열의 각 수를 우선순위큐에 넣음
    pq.offer(i);
    // 우선순위큐의 사이즈가 k보다 커지는 경우 원소를 하나 제거
    // 우선순위큐에는 가장 큰 수부터 k번째 큰 수 까지만 남게됨
    if(pq.size() > k) pq.poll();
}

따라서 모든 탐색이 종료된 후 우선순위큐에 남아있는 요소를 하나 뽑아 return하면 k번째 큰 수를 구할 수 있다.

// 우선순위 큐에 남아있는 k번째 큰 수를 return
return pq.poll();

---

최종 코드

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int i : nums) {
            // num배열의 각 수를 우선순위큐에 넣음
            pq.offer(i);
            // 우선순위큐의 사이즈가 k보다 커지는 경우 원소를 하나 제거
            // 우선순위큐에는 가장 큰 수부터 k번째 큰 수 까지만 남게됨
            if(pq.size() > k) pq.poll();
        }
        
        // 우선순위 큐에 남아있는 k번째 큰 수를 return
        return pq.poll();
    }
}