Runtime O(nlogn)
class Solution { public List<Integer> topKFrequent(int[] nums, int k) { HashMap<Integer, Integer> times = new HashMap<Integer, Integer>(); for(int i=0; i<nums.length; i++) { if(times.get(nums[i])!=null) { times.put(nums[i], times.get(nums[i])+1); } else { times.put(nums[i], 1); } } List<Integer> list = new ArrayList<Integer>(times.keySet()); list.sort((a,b)->times.get(b)-times.get(a)); return list.subList(0,k); } }
Optimized
Runtime O(n)
class Solution { public List<Integer> topKFrequent(int[] nums, int k) { //count the frequency for each element HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int max = 0; for(int num: nums){ if(map.containsKey(num)){ max = Math.max(map.get(num)+1, max); map.put(num, map.get(num)+1); }else{ max = Math.max(max, 1); map.put(num, 1); } } ArrayList<Integer>[] arr = (ArrayList<Integer>[]) new ArrayList[max+1]; for(int i=1; i<=max; i++){ arr[i]=new ArrayList<Integer>(); } for(Map.Entry<Integer, Integer> entry: map.entrySet()){ int count = entry.getValue(); int number = entry.getKey(); arr[count].add(number); } List<Integer> result = new ArrayList<Integer>(); for(int j=max; j>=1; j--){ if(arr[j].size()>0){ for(int a: arr[j]){ result.add(a); if(result.size()==k){ return result; } } } } return result; } }