박종훈 알고리즘 블로그

(Leetcode) 347 - Top K Frequent Elements 풀이

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


https://leetcode.com/problems/top-k-frequent-elements/description/

해결할 수 있는 다양한 방법이 있겠지만, 연습삼아 최대한 stream을 사용하는 방향으로 해결해보았다.

내가 작성한 풀이

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> counter = new HashMap<>();

    Arrays.stream(nums)
            .forEach(num -> counter.merge(num, 1, Integer::sum));

    return counter.entrySet().stream()
            .sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed())
            .mapToInt(Map.Entry::getKey)
            .limit(k)
            .toArray();
}

TC, SC

이 코드의 시간 복잡도는 O(nlogn)이고, 공간 복잡도는 O(n)이다. 빈도를 기준으로 map을 생성하기 때문에 n 보다 적은 경우가 대다수 이겠지만, 최악의 경우 n개의 map entry가 생성될 수 있다. (정렬으로 인해 nlogn 이다.)