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. 这道题用Bucket Sort，新建一个List<Integer>[nums.length + 1]，再新建一个hashmap把所有的数和出现的次数存下来，再以出现次数为索引把把数存到相应的 List<Integer>[i]里，在从后向前遍历k个List<Integer>输出。代码如下：public class Solution { public List<Integer> topKFrequent(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); List<Integer>[] list = new List[nums.length + 1]; List<Integer> res = new ArrayList<Integer>(); for (int num: nums) { map.put(num, map.getOrDefault(num, 0) + 1); } for (int num: map.keySet()) { if (list[map.get(num)] == null) { list[map.get(num)] = new ArrayList<Integer>(); } list[map.get(num)].add(num); } for (int i = nums.length; res.size() < k && i >= 0; i --) { if (list[i] != null) { res.addAll(list[i]); } } return res; } }
