347. 前 K 个高频元素
347. 前 K 个高频元素
给你一个整数数组 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 l o g n ) O(n log n) O(nlogn)，其中 n n n 是数组大小。
思路：
这道题目主要涉及到如下三块内容：
- 要统计元素出现频率
- 对频率排序
- 找出前
k个高频元素
首先统计元素出现的频率，这一类的问题可以使用map来进行统计。
然后是对频率进行排序，可以直接使用库函数进行快速排序，不过时间复杂度是 O ( n l o g n ) O(n log n) O(nlogn)，不太符合题目诉求，题目进阶要求是时间复杂度优于 O ( n l o g n ) O(n log n) O(nlogn)，所以应该想到堆，实际上，求最大或者最小的k个数，大部分时候都是用堆解决的。
什么是堆呢？
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。
思考一下，是使用小顶堆呢，还是大顶堆？
有的同学一想，题目要求前 k 个高频元素，那么果断用大顶堆啊。
那么问题来了，定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前k个高频元素呢。
所以如果使用大顶堆就要把所有元素都进行排序，那能不能只排序k个元素呢？
可以的，我们用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的就是前k个最大元素。
Go 语言对于堆没有现成可使用的库，但是提供了heap包，只要实现 heap.Interface 接口要求的方法，然后，使用 heap.Init 初始化堆，就可以使用这个堆了。
heap包的Interface接口定义如下：
type Interface interface {sort.InterfacePush(x any) // add x as element Len()Pop() any // remove and return element Len() - 1.
}
sort包的Interface接口定义如下：
type Interface interface {Len() intLess(i, j int) boolSwap(i, j int)
}
所以我们要实现heap.Interface，需要实现五个方法。
注意：Len方法直接用h调用，但是Push和Pop方法则是用heap包的，然后将h作为了参数
Go代码如下：
func topKFrequent(nums []int, k int) []int {//使用小顶堆map_num:=map[int]int{}//记录每个元素出现的次数for _,item:=range nums{map_num[item]++}// 初始化堆h:=&IHeap{}heap.Init(h)//所有元素入堆，堆的长度为k// 注意：Len方法直接用h调用，但是Push和Pop方法则是用heap包的，然后将h作为了参数for key,value:=range map_num{heap.Push(h,[2]int{key,value})if h.Len()>k{heap.Pop(h)}}res:=make([]int,k)//按顺序返回堆中的元素for i:=0;i<k;i++{res[k-i-1]=heap.Pop(h).([2]int)[0]}return res
}// 构建小顶堆
type IHeap [][2]intfunc (h IHeap) Len()int {return len(h)
}func (h IHeap) Less (i,j int) bool {return h[i][1]<h[j][1]
}func (h IHeap) Swap(i,j int) {h[i],h[j]=h[j],h[i]
}func (h *IHeap) Push(x interface{}){*h=append(*h,x.([2]int))
}
func (h *IHeap) Pop() interface{}{x:=(*h)[len(*h)-1]*h=(*h)[0:len(*h)-1]return x
}// //方法二:利用O(nlogn)排序
// func topKFrequent(nums []int, k int) []int {
// ans:=[]int{}
// map_num:=map[int]int{}
// for _,item:=range nums {
// map_num[item]++
// }
// for key,_:=range map_num{
// ans=append(ans,key)
// }
// //核心思想：排序
// //可以不用包函数，自己实现快排
// sort.Slice(ans,func (a,b int)bool{
// return map_num[ans[a]]>map_num[ans[b]]
// })
// return ans[:k]
// }
