题目
Given a non-empty array of integers, return the k most frequent elements.
题意
给定一个数组，求出出现频率最高的k个元素
例子
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
题解
很容易想到的解法，就是使用map来存储对应元素出现的频率，然后对出现频率进行排序，求出前k个元素。这样的时间复杂度就取决于排序算法的时间复杂度；
这里使用桶排序的思想，初始化一个桶，按照出现频率分为n个桶（出现频率最高即为n个），然后遍历map将元素存入对应的桶中，逆序遍历桶，即从出现频率最高的桶中依次取出对应的元素，取出k个即止，时间复杂度最n(k) ,所以总的时间复杂度为o(n)；
代码
func topKFrequent(nums []int, k int) []int {
frequency := make(map[int]int)
buckets := make([][]int,len(nums)+1)//桶
result := make([]int,0)
for _,num := range nums{
frequency[num]++
}
for num,times := range frequency{
buckets[times] = append(buckets[times],num)
}
count := k
for i:=len(nums);i>0;i--{//逆序遍历桶
for _,v:=range buckets[i]{
if count!=0{
result = append(result,v)
count--
}
}
}
return result
}
总结
学到一个新的概念，==桶排序==；桶排序的应用挺广的，主要思路就是能够将元素分配到有限数量的桶中；然后每个桶在进行操作。在这道题里，由于最多出现频率为n，所以可以有以频率划分的n个桶，每个桶中存放出现频率相同的元素。那么存放好后自然就排好序了，我们直接从桶中获取就行了；
大部分简单的桶排序都是基于以上的概念；因为桶的数量必须是有限的，所以不可能所有情况都有一个对应的桶，这个时候桶就是对某一范围的划分（桶与桶之间是排序的），所以桶内还需要进行排序；
有点类似快排，可以使用桶来划分一些数据，不关心细节是否排序，而桶与桶之间是排序的。比如前一个桶中的任何一个数据都比后一个桶中的数据大，但桶中并不一定排好序，可以利用这些来解决问题。
