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) { int n = nums.length; List<Integer>[] bucket = new List[n+1]; List<Integer> list = new ArrayList<>(); Map<Integer,Integer> map = new HashMap<>(); for(int i =0 ;i <n; i++) { map.put(nums[i],map.getOrDefault(nums[i],0)+1); } for(int key : map.keySet()) { int temp = map.get(key); if(bucket[temp] == null) { bucket[temp] = new ArrayList<>(); } bucket[temp].add(key); } for(int i = bucket.length -1 ; i>=0 && list.size() < k; i--) { if(bucket[i]!=null) { list.addAll(bucket[i]); } } return list; } }