Top K Frequent Elements

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.

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        //bucket: an array of list  
        List<Integer>[] bucket = new List[nums.length+1];
        Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>(); 
        for (int n: nums) {
            //getOrDefaul: Returns the value to which the specified key 
            //is mapped, or defaultValue (0) if this map contains no 
            //mapping for the key.
            frequencyMap.put(n, frequencyMap.getOrDefault(n,0)+1); 
        }
        for (int key:frequencyMap.keySet()) {
            int frequency = frequencyMap.get(key);
            //high index stands for high frequency 
            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--) {
            //start with the largest index: 
            if (bucket[pos] != null) {
                res.addAll(bucket[pos]);
            }
        }
        return res;
        
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s