문제

https://leetcode.com/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법 1

• 정렬을 사용하지 않고 k 번째로 큰 수를 return 하는 문제
• PriorityQueue(MaxHeap)을 사용하여 해결

코드

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : nums) {
            pq.add(num);
        }

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

결과

해결 방법 2

• 해결 방법 1 보다 더 빠른 해결 방법을 고민해 봄
• 입력의 범위를 보면 개수는 최대 10만개이지만, 숫자의 범위는 2만개(-10,000 ~ +10000) 라는 것을 이용함
• 모든 숫자를 한 번씩 순회하는 것은 이전과 같지만, 마지막에 k번 poll하는 과정에서 최대 10만번 순회할 수 있는데, 이 과정을 최대 2만번으로 줄여 시간을 줄일 수 있었음
  • 크기가 2만인 배열 생성 후 각각의 숫자가 몇 번씩 들어오는지 체크 -> 마지막에는 이 배열만 한 번 순회하면서 결과를 구하는 방식으로 해결

코드

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] numCnt = new int[20001];
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (int num : nums) {
            numCnt[num + 10000] ++;
            max = Math.max(max, num + 10000);
            min = Math.min(min, num + 10000);
        }

        int cnt = 0;
        for (int i = max ; i >= min ; i --) {
            cnt += numCnt[i];
            if (cnt >= k) {
                return i - 10000;
            }
        }
        return -1;
    }
}

결과