题目

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

示例 1:

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

示例 2:

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

说明：

• 可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 算法的时间复杂度必须优于 , n 是数组的大小。

方案一（堆）

type Item struct {
    value int
    count int // 出现次数
}

type Counter []*Item

func (this Counter) Len() int { return len(this) }
func (this Counter) Less(i, j int) bool {
    // We want Pop to give us the highest, not lowest, count so we use greater than here.
    return this[i].count > this[j].count
}
func (this Counter) Swap(i, j int) { this[i], this[j] = this[j], this[i] }
func (this *Counter) Push(x interface{}) {
    item := x.(*Item)
    *this = append(*this, item)
}
func (this *Counter) Pop() interface{} {
    old := *this
    n := len(old)
    item := old[n-1]
    *this = old[0 : n-1]
    return item
}

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

    c := make(Counter, 0)
    heap.Init(&c)
    for num, count := range m {
        item := &Item{
            value: num,
            count: count,
        }
        heap.Push(&c, item)
    }

    ret := []int{}
    for i := 0; i < k; i++ {
        item := heap.Pop(&c).(*Item)
        ret = append(ret, item.value)
    }

    return ret
}

原文

https://leetcode-cn.com/explore/learn/card/hash-table/207/conclusion/829/

https://studygolang.com/pkgdoc

https://leetcode-cn.com/problems/top-k-frequent-elements/solution/leetcode-di-347-hao-wen-ti-qian-k-ge-gao-pin-yuan-/