[코테연습] 347. Top K Frequent Elements

 

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

- 배열문제
- int[] nums = {1,1,1,2,2,3} 이 주어졌을 때, 가장 빈도가 높은 순으로 정렬한다.
- 그리고 k 만큼 배열을 잘라서 리턴한다.

- 해결 순서
1. HashMap 으로 nums 의 각 element가 몇 개 있는지 갯수를 센다.
2. List<List<Integer>> graph 리스트를 초기화 하여 가장 큰 element 만큼 초기화한다.
3. graph 리스트에 HashMap 의 value 위치에 key 를 저장한다. => graph.get(value).add(key);
4. graph 리스트를 for 문으로 돌리면서 int[] arr = new int[k];  배열에 k 값 이전 만큼 숫자를 넣는다.

 

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
      
        Arrays.sort(nums);

        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int i= 0; i < nums.length;i++) {
            int key = nums[i];
            int count = map.getOrDefault(key, 0)+1;
            max = Math.max(max, count);
            map.put(key, count);
        }

        int size = max+1;
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < size; i++) {
            graph.add(new ArrayList<>());
        }

        for (int key : map.keySet()) {
            int value = map.get(key);
            graph.get(value).add(key);
        }


        int[] rs = new int[k];
        int index = 0;
        for(int i = graph.size()-1; i >= 0; i--) {
            List<Integer> list = graph.get(i);
            if (!list.isEmpty()) {
                for(int j = 0; j < list.size(); j++) {
                    if (index < k) {
                        rs[index++] = list.get(j);
                    }
                }
            }
        }
        return rs;
    }
}