347.Top K Frequent Elements

1 - HashTable + BucketSort O(n)

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

        // corner case: if there is only one number in nums, we need the bucket has index 1.
        List<Integer>[] bucket = new List[n + 1];

        for(Integer i : map.keySet()){
            int freq = map.get(i);
            if(bucket[freq] == null){
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(i);
        }
        List<Integer> res = new ArrayList<>();
        for(int i = n; i > 0 && k > 0; i--){
            if(bucket[i] != null){
                res.addAll(bucket[i]);
                k -= bucket[i].size();
            }
        }
        return res;
    }
}