[Medium] Kth Largest Element in an Array (아마존/구글)

#문제 설명

Leetcode 215번 문제는 정수로 채워진 배열 nums와 정수 k가 주어진다. 주어진 배열안에서 k번째로 큰 정수를 return하면 된다. 위에 예시를 보면 [3,2,1,5,6,4] 의 배열과 k=2가 주어진다 이경우 에는 배열에서 2번째로 큰 숫자를 return하면 되기에 5를 return해야한다. 

#문제 풀이

Min-heap 풀이:

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //min-heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for(int i = 0; i < k;i++){
            minHeap.add(nums[i]);
        }

        for(int i = k; i < nums.length;i++){
           if(minHeap.peek() < nums[i]){
               minHeap.poll();
               minHeap.add(nums[i]);
           }
        } 
        return minHeap.peek();
    }
}

 이 풀이는 min-heap를 사용한 풀이이다. 먼저 min-heap를 만들고, min heap에 각 배열을 복사해주면 된다. 그리고 만들어진 min heap에 loop를 해주면서 min heap의 root가 nums[i]보다 작을시 root를 poll해주고 minheap에 nums[i]를 add시켜주면 된다.

Max-heap 풀이:

 

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //max-heap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for(int i = 0; i < nums.length;i++){
            maxHeap.add(nums[i]);
        }

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

Max-heap풀이에서는 maxheap를 만들고 k-1까지만 loop해주면서 root를 poll해주면 된다