Top K Frequent Elements


#1

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

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

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.

#2

The below code uses bucket sort, where the buckets are made of the frequency count.

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        List<Integer>[] buckets = new ArrayList[nums.length+1];
        for(int num : map.keySet()){
            int freq = map.get(num);
            if(buckets[freq]==null) buckets[freq] = new ArrayList<>();
            buckets[freq].add(num);
        }
        List<Integer> result = new ArrayList<>();
        for(int i=buckets.length-1; i>=0 && result.size()<k ;i--){
            if(buckets[i]!=null)
                result.addAll(buckets[i]);
        }
        
        return result;
    }
}