[LeetCode] 215. Kth Largest Element in an Array

215. Kth Largest Element in an Array

문제 분석

정수 배열과 정수 k 가 하나 주어졌을 때 k 번째로 큰 요소를 반환하는 문제.

단, 정렬을 이용하지 않고 해결해야 한다.

풀이 과정

자바에서 Heap 을 구현한 데이터 구조 중 하나인 우선순위 큐 를 이용하여 접근하였다.

요소들을 저장하고 우선순위에 따라 요소들을 추출할 수 있다.

주어진 배열을 우선순위 큐 에 담은 후 k 만큼 poll() 해 제거해준다.

나의 생각

우선순위 큐에 대한 내부 구조를 좀 더 깊이 이해한다면 시간 복잡도 성능을 더 줄일 수 있을 것 같다.

코드


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

        for (int i : nums) {
            pq.offer(i);
        }

        for (int i = 0; i < k - 1; i++) {
            pq.poll();
        }

        return pq.poll();
    }
}