.jpg)
564 字
3 分钟
前 K 个高频元素
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
解题思路
- 频率统计：遍历数组，使用哈希表记录每个元素出现频率。
- 桶排序优化：创建长度为
n+1的桶数组，以频率为下标存储对应元素。 - 逆序收集：从最高频率桶（最大下标）开始，收集元素直到获得 k 个结果。
- 提前终止：当结果集达到 k 个元素时立即返回。
关键洞察
- 桶索引即频率：利用频率与数组索引的等价性，实现 O(1) 频率分组。
- 空间换时间：桶数组将排序复杂度从 O(n log n) 降至 O(n)。
- 频率边界明确：元素频率必在 [1, n] 范围内，避免无效桶空间。
- 同频元素批量处理：相同频率元素存储在同一桶中，简化收集逻辑。
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：统计频率 O(n) + 构建桶 O(n) + 收集结果 O(n) |
| 空间复杂度 | O(n)：哈希表 O(n) + 桶数组 O(n)（最坏情况需存储所有元素） |
代码实现
/** * 哈希 + 桶排序 * @link {https://leetcode.cn/problems/top-k-frequent-elements} * @param {number[]} nums * @param {number} k * @return {number[]} */var topKFrequent = function (nums, k) { const cnt = new Map(); for (const x of nums) { cnt.set(x, (cnt.get(x) ?? 0) + 1) } const maxCnt = Math.max(...cnt.values());
const buckets = Array.from({ length: maxCnt + 1 }, () => []); for (const [x, c] of cnt.entries()) { buckets[c].push(x); }
const ans = []; for (let i = maxCnt; i >= 0 && ans.length < k; i--) { ans.push(...buckets[i]) }
return ans;}实际应用场景
- 热门关键词提取：分析搜索日志中的高频词汇`
- 用户行为分析：电商平台购买频率最高的商品`
- 网络监控：检测高频访问IP地址`
- 推荐系统：根据点击频率推荐内容`