본문 바로가기

2. 알고리즘 공부/JAVA 리트코드 풀이

[Leetcode] 347. Top K Frequent Elements

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

 

Loading...

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

1. Problem 

비어있지 않은 정수 배열이 주어졌을 때, 가장 많이 등장하는 k개의 원소를 반환하라

Given a non-empty array of integers, return the k most frequent elements.

 

 

2. Algorithm

Step 1. 배열이 주어지면, 각 원소가 등장하는 횟수를 세어주자. -> O(n)

Once the array is given, count the times each element appears. (I will use HashMap, so it takes O(n))

 

Step 2. 그다음 그 Map을 정렬하는데 등장횟수를 기준으로, List에 다시 넣어서(n) 내림차순 정렬을해준다 -> O(klgk)

After that, sort the numbers with times each element appears by dsc order. (Sorting takes another O(klogk))

 

Step 3. 마지막으로 ans 리스트에 k-1번째 원소까지 담아 리턴한다. 단, 횟수가 같은 원소가 있을 수 있기 때문에 k번째 원소 이후에도 등장횟수가 같은애가 존재하면 ans배열에 추가해준다. -> O(k)

Cut the sorted list to index k-1. But, there might exist number with same count, so check it and add if it exists.

 

n + 2k + klgk으로, O(NlogN) 솔루션이다.

This is my O(NlogN) solution.

 

class Solution {
    class Number {
        int num;
        int cnt;
	    Number(int n, int c) {
            num = n;
            cnt = c;
        }
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Number> list = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        
        // Step1
        for(int n:nums) map.put(n, map.getOrDefault(n, 0)+1); 
        // Step2
        for(int n: map.keySet()) list.add(new Number(n, map.get(n))); 
        Collections.sort(list, (a, b) -> b.cnt - a.cnt);
        // Step3
        for(int i = 0; i < list.size(); i++) {
            if (i >= k && list.get(i).cnt < list.get(k-1).cnt) break;
            ans.add(list.get(i).num);
        }
        return ans;
    }

}

 

 

3. retrospective

 

런타임이 37퍼센트 정도 밖에 안된다는 것은 더 좋은 솔루션이 있다는 뜻이다. HashMap+Heap 조합으로 푸는 솔루션도 존재하지만, 런타임이 40퍼센트대인 것을 보아서 최고의 방법은 아닌 것 같다. 더 좋은 방법이 무엇이 있을지도 더 생각해볼 여지가 있는 문제이다.

My code hits 37% runtime which mean that there are more better solution that mine. In the leetcode, I found some solutions with HashMap and Heap combination, but it also hits only 40% runtime so it is not the best one. I want to find some outstanding idea than this.