(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.put(num, counter.getOrDefault(num, 0) + 1);
});
return Arrays.copyOfRange(counter.entrySet().stream()
.sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed())
.mapToInt(Map.Entry::getKey)
.toArray(), 0, k);
}
TC, SC
이 코드의 시간 복잡도는 O(nlogn)이고, 공간 복잡도는 O(n)이다. 빈도를 기준으로 map을 생성하기 때문에 n 보다 적은 경우가 대다수 이겠지만, 최악의 경우 n개의 map entry가 생성될 수 있다. (정렬으로 인해 nlogn 이다.)