摘要：题目要求假设有一个非空的整数数组，从中获得前个出现频率最多的数字。先用来统计出现次数，然后将其丢到对应的桶中，最后从最高的桶开始向低的桶逐个遍历，取出前个频率的数字。
题目要求
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.
假设有一个非空的整数数组，从中获得前k个出现频率最多的数字。
思路和代码
这里有一个额外要求即时间复杂度要优于O(n log n)，也就是说我们无法采用先排序再顺序计算的方式来进行统计，因为最好的排序算法其平均的时间复杂度也需要O(n log n)。那么有没有别的方法可以让我们达到更好的效率呢？
这里的核心思路是桶排序，我们通过使用n+1个桶（其中第i个桶代表出现i次的数据）来汇拢每个数字出现的次数。先用HashMap来统计出现次数，然后将其丢到对应的桶中，最后从最高的桶开始向低的桶逐个遍历，取出前k个频率的数字。
public List topKFrequent(int[] nums, int k) {
List[] buckets = new List[nums.length + 1];
Map frequency = new HashMap();
for(int num : nums){
frequency.put(num, frequency.getOrDefault(num, 0) + 1);
}
for(int key : frequency.keySet()){
int frequencyOfKey = frequency.get(key);
if(buckets[frequencyOfKey] == null){
buckets[frequencyOfKey] = new ArrayList();
}
buckets[frequencyOfKey].add(key);
}
List result = new ArrayList();
for(int i = buckets.length-1 ; i>=0 && k>result.size() ; i--){
if(buckets[i] != null){
result.addAll(buckets[i]);
}
}
return result;
}
想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/69314.html
