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 分析思路： 借鉴统计字符串中每个字符的个数的思想，用频数作为数组的下标 1.利用map结构统计每个数字的频数 2.初始化list数组，注意这里数组长度是输入数字的个数 3.以频数作为数组下标，初始化list，并添加相应的key 4.倒序添加频数多的，直到个数大于k结束 public class Solution { public List<Integer> topKFrequent(int[] nums, int k) { if(nums==null||nums.length==0||k<=0){ return null; } Map<Integer,Integer> frequencyMap = new HashMap<Integer,Integer>(); /**************get each element frequency *****************/ for(int n:nums){ if(frequencyMap.containsKey(n)){ frequencyMap.put(n, frequencyMap.get(n)+1); }else frequencyMap.put(n, 1); } List<Integer>[] bucket = new List[nums.length]; /******************generate list[] by frequency*****************/ for(int key:frequencyMap.keySet()){ int v = frequencyMap.get(key); if(bucket[v-1]==null){ bucket[v-1] = new ArrayList<Integer>(); } bucket[v-1].add(key); } List<Integer> result = new ArrayList<Integer>(); label: for(int i=bucket.length-1;i>=0;i--){ if(bucket[i]!=null){ for(Integer num:bucket[i]){ if(result.size()<k){ result.add(num); }else break label; } } } return result; } }