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.
[code lang="java"]
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        
    }
}
[code]

Idea – 1

We use a hash map to save the frequency of each element. Next we put the keys in a min heap of size k (whenever the heap becomes bigger than k we throw away top which is the least frequent element). At the end we have k most frequent elements in the heap. Time complexity is O(n\cdot lg{k}) and space complexity is O(n). 
[code lang="java"]
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int x : nums)
        {
            map.put( x, map.getOrDefault(x, 0)+1 );
        }
        
        PriorityQueue<Integer> minq = new PriorityQueue<>( (a, b) -> ( map.get(a)-map.get(b) ) );
        for(int key : map.keySet())
        {
            minq.offer(key);
            if(minq.size() > k)
            {
                minq.poll();
            }
        }
        
        while(!minq.isEmpty())
        {
            ans.add(minq.poll());
        }
        
        return ans;
    }
}
[code]

Runtime: 42 ms, faster than 42.71% of Java online submissions for Top K Frequent Elements.Memory Usage: 39.1 MB, less than 65.70% of Java online submissions for Top K Frequent Elements.

Leave a comment