[LeetCode 75] 215. Kth Largest Element in an Array

 

import java.util.Arrays;
import java.util.Collections;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Integer[] numsWrapper = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(numsWrapper, Collections.reverseOrder());
        return numsWrapper[k - 1];
    }
}

 

문제가 너무 쉬워서 아주 빨리 풀었는데 배열을 재정렬 하기 때문에 시간 복잡도가 O(n log n)이다..

 

💡 풀이 포인트

• min-heap 활용
  • PriorityQueue는 기본적으로 최소 힙을 생성한다.
• 힙의 크기를 k로 유지하기 때문에 힙의 루트 값(peek()) = k번째로 큰 값
• 배열의 각 요소를 힙에 넣고 힙의 크기가 k보다 커지면 poll()로 가장 작은 요소 제거
• 이 외에 Quickselect 알고리즘 사용하는 방법이 있으나 코드가 길었음.

import java.util.PriorityQueue;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // 배열의 각 요소를 처리
        for (int num : nums) {
            // 힙에 추가
            minHeap.offer(num);
            
            // 힙의 크기가 k보다 크면 가장 작은 요소를 제거
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        // k번째로 큰 값 반환
        return minHeap.peek();
    }
}