LeetCode 215 Kth Largest Element in an Array 풀러가기

문제

int 배열 nums 와 숫자 k 가 주어진다.

nums를 정렬했을 때 k 번째로 큰 숫자를 반환해라.

k번째로 큰 숫자는 고유한 k 번째로 큰 숫자를 의미하는 것이 아니다.

nums를 sort하지 않고, 숫자를 반환하는 알고리즘을 구해라.

문제 분석

첫번째 시도 (우선순위큐)

nums를 sorting 하지 않으려면 다른 자료구조를 생각해야 했다.

나는 우선순위큐를 사용해서, 각 숫자를 담고, k번 만큼 빼는 알고리즘을 구했다.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((p1,p2)->p2-p1);
        for(int i=0; i<nums.length; i++){
            pq.add(nums[i]);
        }

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

        return answer;

    }
}

결과 : 성공

Runtime

Memory

런타임이나, 메모리가 좋지 않았다.

pq의 insert가 O(logn)이고, 그게 n번만큼 반복되니 O(nlogn+k)의 시간복잡도를 가지는 코드였다.

더 줄이는 방법을 고민해보았다.

다른방법 시도 (Arrays.sort)

문제에서 sorting을 하지 말고 다른 방법이 있나 물어보았지만,

sort 함수의 시간복잡도가 O(nlogn)의 시간복잡도이니 한번 시도해보았다.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}

결과 : 성공

Runtime

Memory

이전 코드보다 20ms이상 시간이 감소했다.

이 두가지 방법 말고 다른 방법이 있는지 고민해봐야겠다.