leetcode-347-Top K Frequent Elements

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.

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i=0; i<nums.length; i++)
            map.put(nums[i], map.containsKey(nums[i]) ? map.get(nums[i]) + 1 : 1);
        
        List<Map.Entry<Integer, Integer>> list = new LinkedList<>(map.entrySet());
        
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>(){
           public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2){
               return o2.getValue().compareTo(o1.getValue());
           }
        });
        
        List<Integer> res = new ArrayList<>();
        for(int i=0; i<k; i++)
            res.add((Integer) list.get(i).getKey());
        return res;
    }
}