215. Kth Largest Element in an Array

문제

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

풀이

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

        for(int n : nums) {
            heap.add(n);
        }

        int answer = 0;

        for(int i = 0; i < k; i++) {
            answer = heap.poll();
        }

        return answer;
    }
}

• 정렬없이 O(NlogN)의 시간복잡도
  • heap에 add하는데 O(NlogN), poll하는데 k만큼 O(NlogN)
    • poll하면 재정렬하는데 O(NlogN)만큼의 시간이 걸림