前K个高频元素

1. 题目描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

2. 思路

1. 思路一
   • 使用map对数量进行统计
   • 然后根据数量进行排序
2. 思路二
   • 使用map对数量进行统计
   • 最小堆

3. 实现

3.1. map

func topKFrequent(nums []int, k int) []int {
    m := make(map[int]int, 0)
    for _, num := range nums {
        m[num] += 1
    }
    lst := make([]int, 0, len(m))
    for k,_ := range m {
        lst = append(lst, k)
    }
    sort.Slice(lst , func(i, j int) bool {
        return m[lst[i]] > m[lst[j]]
    })
    return lst[:k]
}

3.2. 最小堆

type item struct {
	num   int
	count int
}

type itemHeap struct {
	items []*item
}

func (h *itemHeap) Len() int {
	return len(h.items)
}

func (h *itemHeap) Less(i, j int) bool {
	return h.items[i].count < h.items[j].count
}

func (h *itemHeap) Swap(i, j int) {
	h.items[i], h.items[j] = h.items[j], h.items[i]
}

func (h *itemHeap) Push(x interface{}) {
	h.items = append(h.items, x.(*item))
}

func (h *itemHeap) Pop() interface{} {
	num := h.items[len(h.items)-1]
	h.items = h.items[:len(h.items)-1]
	return num
}

func topKFrequent(nums []int, k int) []int {
	m := make(map[int]int, 0)
	for _, num := range nums {
		m[num]++
	}

	h := &itemHeap{}
	for num, count := range m {
		if h.Len() < k {
			heap.Push(h, &item{
				num:   num,
				count: count,
			})
		} else {
			top := h.items[0]
			if top.count < count {
				heap.Pop(h)
				heap.Push(h, &item{
					num:   num,
					count: count,
				})
			}
		}
	}

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

4. 参考

• 347. 前 K 个高频元素 - 前 K 个高频元素 - 力扣（LeetCode）