前 K 个高频元素

怎样从“nums 前 2 高频 [1,2]。”推导出 堆 · 前 K 高频，并证明每次状态变化都不会漏掉答案？

中心结论：频次 map + min-heap k 或 bucket sort。

给一个非空的数组，输出前 K 个频率最高的元素。

在本站主例中，nums 前 2 高频 [1,2]。

算法最终需要得到或观察：[1,2] 频率最高。

每轮在全部元素中重新寻找最值会重复扫描；堆持续维护下一位最值得处理的候选。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“优先级候车区”，明确答案需要观察什么。
2. 2状态只维护 freq map、堆/桶。
3. 3转移每一步按照 频次 map + min-heap k 或 bucket sort。
4. 4收尾读取 [1,2] 频率最高。，并复核边界与复杂度。

先确定堆顶语义，再确定超过容量时淘汰谁。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：freq map、堆/桶。

这一题是考察优先队列的题目。把数组构造成一个优先队列，输出前 K 个即可。

频次 map + min-heap k 或 bucket sort。

执行过程中持续维护：freq map、堆/桶。

正确性依赖以下不变量：桶索引=频率可 O(n)。

面试时可以压缩为：map+heap 或 bucket O(n)。

落到当前题，执行机制可以压缩为：频次 map + min-heap k 或 bucket sort。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums 前 2 高频 [1,2]。 因为：频次 map + min-heap k 或 bucket sort。
2. 2先统计频次,再用堆取 TopK哈希计数 O(n)。 因为：TopK 问题先降维到频次。
3. 3元素 3 频次 1,维护 Top2 堆按频次维护小根堆。 因为：堆顶是 TopK 中的最低频,可被淘汰。
4. 4元素 2 频次 2,维护 Top2 堆按频次维护小根堆。 因为：堆顶是 TopK 中的最低频,可被淘汰。
5. 5元素 1 频次 3,维护 Top2 堆按频次维护小根堆。 因为：堆顶是 TopK 中的最低频,可被淘汰。
6. 6前 2 高频: 2, 1返回堆中元素。 因为：O(n + m log k),m 为不同元素数。
7. 7先统计频次,再用堆取 TopK哈希计数 O(n)。 因为：TopK 问题先降维到频次。
8. 8收尾与复杂度[1,2] 频率最高。 因为：时间 O(n) · 空间 O(1)。频次 map + min-heap k 或 bucket sort。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import "container/heap"

func topKFrequent(nums []int, k int) []int {
	m := make(map[int]int)
	for _, n := range nums {
		m[n]++
	}
	q := PriorityQueue{}
	for key, count := range m {
		heap.Push(&q, &Item{key: key, count: count})
	}
	var result []int
	for len(result) < k {
		item := heap.Pop(&q).(*Item)
		result = append(result, item.key)
	}
	return result
}

// Item define
type Item struct {
	key   int
	count int
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	// 注意：因为golang中的heap是按最小堆组织的，所以count越大，Less()越小，越靠近堆顶.
	return pq[i].count > pq[j].count
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

// Push define
func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(*Item)
	*pq = append(*pq, item)
}

// Pop define
func (pq *PriorityQueue) Pop() interface{} {
	n := len(*pq)
	item := (*pq)[n-1]
	*pq = (*pq)[:n-1]
	return item
}

func main() {
    // 1. 主例
    //    输入：mode="top-k-frequent", nums=[1,1,1,2,2,3], k=2
    //    期望：[1,2] 频率最高。
    //
    // 2. 失败 / 未命中
    //    检查：堆法 O(n log k) 通用。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC215 第 K 大；LC692 TopK 列表
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums 前 2 高频 [1,2]。
2. 2重复每轮在全部元素中重新寻找最值会重复扫描；堆持续维护下一位最值得处理的候选。
3. 3优化频次 map + min-heap k 或 bucket sort。
4. 4证明桶索引=频率可 O(n)。
5. 5复杂度时间 O(n)，空间 O(1)