박종훈 알고리즘 블로그

(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 -> {
                Integer count = counter.get(num);
                counter.put(num, count == null ? 1 : count + 1);
            });

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

이 코드의 시간 복잡도는 O(nlogn)이고, 공간 복잡도는 O(n)이다. (정렬으로 인해 nlogn 이다.)