347. Top K Frequent Elements

Problem:

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

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: 

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Analysis:

Bucket sort. Use List<Integer>[] to sort the frequency. Index is the frequency, the numbers in the bucket[frequency]  list have the frequency in the array.

Solution:

Note bucket has to initialize to be length of nums.length + 1. Frequency is 1 based. 

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer>[] bucket = new List[nums.length + 1];
        
        for (int n: nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        // get distinct numbers
        for (int n: map.keySet()) { 
            int frequency = map.get(n);
            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }
            bucket[frequency].add(n);
        }

        for (int i = bucket.length - 1; i > 0; i--) {
            if (bucket[i] != null) {
                for (int j = 0; j < bucket[i].size() && res.size() < k; j++) {
                    res.add(bucket[i].get(j));
                }
            }
        }

        return res;
    }
}