Top K frequent Elements

Question

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

Solution

由於這題要求要在 O(nlogn) 解出來，之前上九章的時候老師有提到要從 n² 降到 log 有兩個方法：可以排序或選擇 logn 的數據結束再乘以 n。因此這題我的想法是先遍歷，然後把數字更新在 HashMap 上，最後 sort。需要注意的地方為：

1. 要對 Map 的 Value 做 sort，要重寫 comparator

   Collections.sort( list, new Comparator<Map.Entry<>>(){
    public int compare(Object o1, Object o2) {
        return o2.getValue.compareTo(o1.getValue());
    }
   });
   

public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> result = new ArrayList<Integer>();
        if (nums.length <= 0) {
            return result;
        }

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }

        Set<Map.Entry<Integer, Integer>> set = map.entrySet();
        List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(set);

        Collections.sort( list, new Comparator<Map.Entry<Integer, Integer>>() {
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return (o2.getValue().compareTo(o1.getValue()));
            } 
        });

        for(Map.Entry<Integer, Integer> entry : list) {
            if (result.size() != k) {
                result.add(entry.getKey());
            } else {
                break;
            }
        }
        return result;
    }

後來看了解答，發現可以用 O(N) 來解這題，當然還有其他解法：

1. Bucket Sort - O(N)
2. MaxHeap
3. TreeMap

Bucket sort: 建立一個 list[] 當作 bucket，然後把次數當作 index 存進 bucket 裡，就等於自動排好序了

List<Integer>[] bucket = new List[nums.length + 1];
    Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();

    for (int n : nums) {
        frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
    }

    for (int key : frequencyMap.keySet()) {
        int frequency = frequencyMap.get(key);
        if (bucket[frequency] == null) {
            bucket[frequency] = new ArrayList<>();
        }
        bucket[frequency].add(key);
    }

    List<Integer> res = new ArrayList<>();

    for (int pos = bucket.length - 1; pos >= 0 && res.size() < k; pos--) {
        if (bucket[pos] != null) {
            res.addAll(bucket[pos]);
        }
    }
    return res;

MaxHeap = PriorityQueue

public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = 
                         new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            maxHeap.add(entry);
        }

        List<Integer> res = new ArrayList<>();
        while(res.size()<k){
            Map.Entry<Integer, Integer> entry = maxHeap.poll();
            res.add(entry.getKey());
        }
        return res;
    }

treeMap = Use freqncy as the key so we can get all freqencies in order

public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }

        TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
        for(int num : map.keySet()){
           int freq = map.get(num);
           if(!freqMap.containsKey(freq)){
               freqMap.put(freq, new LinkedList<>());
           }
           freqMap.get(freq).add(num);
        }

        List<Integer> res = new ArrayList<>();
        while(res.size()<k){
            Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
            res.addAll(entry.getValue());
        }
        return res;
    }