前 K 个高频元素
题目
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]示例 2:
输入: nums = [1], k = 1
输出: [1]思路
这道题目主要涉及到如下三块内容：
- 要统计元素出现频率
- 对频率排序
- 找出前K个高频元素
首先统计元素出现的频率，这一类的问题可以使用map来进行统计。
然后是对频率进行排序，这里我们可以使用优先级队列。
解法
使用优先队列实现：
// 先封装一个优先级队列
import "container/heap"
type pair struct {
num int
count int
}
type pairHeap []pair
func (h pairHeap) Len() int { return len(h) }
func (h pairHeap) Less(i, j int) bool { return h[i].count < h[j].count }
func (h pairHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *pairHeap) Push(x interface{}) {
*h = append(*h, x.(pair))
}
func (h *pairHeap) 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 {
m := make(map[int]int)
for _, v := range nums {
m[v]++
}
h := &pairHeap{}
heap.Init(h)
for key, value := range m {
if h.Len() < k {
heap.Push(h, pair{key, value})
} else if value > (*h)[0].count {
heap.Pop(h)
heap.Push(h, pair{key, value})
}
}
res := make([]int, k)
for i := 0; i < k; i++ {
res[i] = (*h)[i].num
}
return res
}使用快排实现(使用"sort"包)：
import "sort"
func topKFrequent(nums []int, k int) []int {
m := make(map[int]int{})
for _, v := range nums {
m[v]++
}
var unique []int{}
for key := range m {
unique = append(unique, key)
}
sort.Slice(unique, func (a, b int) bool {
return m[unique[a]] > m[unique[b]]
})
return unique[:k]
}