347. 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.

Analysis:

Approach#1:

Use bucket sort, bucket index represent frequency, max frequency is length of array.(number of elements)

First scan, use map to count elements store in map.

Second scan all map entries, based on count add key to the list in correspond bucket[i]

Third scan all bucket[] backwards, if not null then add all list element to returnlist till returnlist.size() == k

Approach#2:

HashMap + MaxHeap

First scan, count store in map. Second scan all entries, add to heap. Third scan, poll from heap and add to returnList till listsize == k.

Code:(HashMap + MaxHeap Time complexity: O(nlogn))

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        PriorityQueue<Map.Entry<Integer, Integer>> maxheap = new PriorityQueue<Map.Entry<Integer, Integer>>(nums.length, new Comparator<Map.Entry<Integer, Integer>>(){
            @Override
            public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b)
            {
                return b.getValue().compareTo(a.getValue());
            }
        });

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int itr : nums)
        {
            map.put(itr, map.getOrDefault(itr, 0) + 1);
        }

        for(Map.Entry<Integer, Integer> itr : map.entrySet())
        {
            maxheap.offer(itr);
        }

        List<Integer> returnList = new ArrayList<Integer>();
        while(returnList.size() < k)
        {
            returnList.add(maxheap.poll().getKey());
        }

        return returnList;
    }
}