刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/top-k-frequent-elements/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <= 10^5
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

思路

经典 TOPK，应该会很容易往堆上联想，我开始也是直接写的堆排，过了，但是时间复杂度排名比较低，所以感觉应该还有更快方法。

继续思考别的思路，在统计了数字频次的基础上，突然发现 桶排序 的思路似乎很适合：

• 这里我们可以根据频次分桶，从频次高到低，自然有了一个排序
• 但是桶内元素我们并不需要再排序了，直接照单全收即可
• 题目保证了结果集唯一，所以不用考虑桶内元素全收之后，结果集个数多余 k 的情况

这样一来，复杂度降低到了 O(n)，当然，空间复杂度肯定会高一些了

大体思路就是这样了，上代码～

代码

桶排序

func topKFrequent(nums []int, k int) []int {

	// 统计 num => count
	countMap := make(map[int]int, len(nums))
	for _, num := range nums {
		countMap[num]++
	}

	// 桶排序 count => []{num1, num2, ...}
    // 注意初始化，会产生很多空桶
	bucket := make([][]int, len(nums)+1)
	for num, count := range countMap {
		if bucket[count] == nil {
			bucket[count] = make([]int, 0)
		}
		bucket[count] = append(bucket[count], num)
	}

	// 从大到小看桶里是否非空，非空则加入结果集，够数了就退出
	res := make([]int, 0, k)
	for i := len(bucket) - 1; i >= 0; i-- {
		// 非空桶跳过
		if len(bucket[i]) > 0 {
			res = append(res, bucket[i]...)
            // 够数了就撤
			if len(res) >= k {
				break
			}
		}
	}
	return res
}

堆排

type minheap [][]int

func (h minheap) Less(i, j int) bool {
	return h[i][1] < h[j][1]
}

func (h minheap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h minheap) Len() int {
	return len(h)
}

func (h *minheap) Push(x interface{}) {
	*h = append(*h, x.([]int))
}

func (h *minheap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func topKFrequent(nums []int, k int) []int {

	kvMap := make(map[int]int, len(nums))
	for _, v := range nums {
		kvMap[v]++
	}

	h := &minheap{}
	for kNum, v := range kvMap {
		heap.Push(h, []int{kNum, v})
		if h.Len() > k {
			heap.Pop(h)
		}
	}

	res := make([]int, 0, k)
	for i := 0; i < k; i++ {
		res = append(res, (*h)[i][0])
	}
	return res
}