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.找出频率最高的k个数：
class Solution { public List<Integer> topKFrequent(int[] nums, int k) { Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>(); for (int n : nums) { frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1); } List<Integer>[] bucket = new List[nums.length + 1];//数字的频率最小为0,最大为n for (int key : frequencyMap.keySet()) { int frequency = frequencyMap.get(key); if (bucket[frequency] == null) {//bucket[i]里面放的是所有频率为i的数 bucket[frequency] = new ArrayList<>(); } bucket[frequency].add(key); } List<Integer> res = new ArrayList<>(); for (int pos = bucket.length - 1; pos >= 0; pos--) {//从最高频率的数开始 if (bucket[pos] != null) { res.addAll(bucket[pos]); if(res.size() >= k){//已经满了或者破了 break; } } } return res.subList(0,k); } }
