前 K 个高频元素
Top K Frequent Elements
返回数组中出现频率最高的 k 个元素，顺序不限。
在力扣中练习题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
解题思路
主解法
频率表 + 桶排序
用出现次数当桶下标，从高到低取满 k 个
先统计每个元素的出现次数。频率的范围只有 1..n，所以可以开一个长度为 n+1 的桶数组，把元素放进“出现次数”对应的桶里。
分步图解
先统计频率，再按“出现次数”建桶；最后从高次数往低次数取满 2 个。
然后从 n 向下扫描桶，先取高频率桶里的元素，取满 k 个就停止。这样不需要对所有不同元素排序，时间 O(n)。
自拟数组中 7 出现 4 次、5 出现 3 次，k=2，直接从 4 次桶和 3 次桶各取一个，得到 [7,5]。
分步图解
按次数放入桶：4 次桶放 7，3 次桶放 5，2 次桶放 2，1 次桶放 9。
桶排序的代价是需要 O(n) 的桶空间；如果不同元素很少、k 也很小，用小顶堆 O(n log k) 更省空间。
时间 O(n)，空间 O(n)。
时间 O(n)空间 O(n)
易错点
- 桶下标用元素值而不是频率：频率范围才是 1..n。
- 从低频率往高扫描：会先取到最不频繁的元素。
- 取满 k 个后不 break：可能多取元素。
- 用 unordered_map 遍历顺序当答案顺序：题目不要求顺序，但调试时不要依赖它。
代码与演示
演示输入
nums = [5,5,5,2,2,7,7,7,7,9]，k = 2先统计频率，再按“出现次数”建桶；最后从高次数往低次数取满 2 个。
查看 C++ 代码
延伸阅读
- “频率范围有限”是桶排序的关键条件；如果频率没有上界，就不能直接开数组。
- 另一种常见写法是维护大小为 k 的小顶堆，按频率淘汰，时间 O(n log k)、空间 O(n)。