[Leetcode] 347. Top K Frequent Elements

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

Loading...

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.