[LeetCode] 215. Kth Largest Element in an Array

Kth Largest Element in an Array - LeetCode

정수 배열 num과 정수 k가 주어지면 배열에서 k번째로 큰 요소를 반환합니다.
k번째 고유 요소가 아니라 정렬된 순서에서 k번째로 큰 요소라는 점에 유의하세요.

+ 정렬하지 않고 풀 수 있는지도 물어봅니다!

 

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

 

문제 접근

배열에서 k번째로 큰 요소를 반환하는 것입니다.

그런제 정렬을 하지 않고 풀라고 합니다.

 

그럼 Heap을 사용하는 PriorityQueue를 사용해서 풀 수 있을것 같습니다.

 

PriorityQueue는 Defalute가 오름차순 정렬이기 때문에

람다식을 통해 Comparator를 구현하였습니다.

 

이후 k번째까지 loop를 돌면서 ret에 값을 담아 리턴하였습니다. 

	public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        for (int num : nums) {
            pq.add(num);
        }

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

        return ret;
    }

 

느낀점

PriorityQueue를 잘활용하면 삽입과 삭제를 O(log N)안에 할 수 있습니다.

상황에 따라 잘 활용해야겠습니다!