Kth Largest Element in an Array

Pretty simple Question!

Find the Kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

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

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

알고리즘 #1 K번째 큰 원소는 정렬된 상태의 배열에서 [배열의 길이-K] 방에 있는 원소다! 1. 배열 오름차순 정렬 - Arrays.sort() 이용 2. K번째 큰 원소 리턴 - nums[nums.length-K]

알고리즘 #2 우선선위 큐(오름차순 정렬, 최소힙)를 이용하여 푼다. 1. 오름차순의 최소힙 큐를 생성하고 배열의 데이터를 큐에 넣는다. - .offer() 2. K크기 만큼의 큐를 유지한다. - .poll() 3. 마지막에 큐의 헤드를 리턴한다. - .peek()

class Solution {
    public int findKthLargest(int[] nums, int k) {
        
        //1. Array로 풀기
        int length = nums.length;
        Arrays.sort(nums);
        return nums[length-k];
        //2. PriorityQueue로 풀기
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Comp);
        for(int i:nums) {
            pq.offer(i);
            if(pq.size() > k) {
                pq.poll();
            }
        }
        return pq.peek();
    }
    
    Comparator<Integer> Comp = new Comparator<Integer>() {
        public int compare(Integer a, Integer b) {
            return a-b;
        }
    };
}