【LeetCode热题100道笔记】前 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
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

**进阶：**你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

思考一：优先队列

先用哈希表统计每个元素的频次，花费时间$O(n)$；再创建一个容量为 k 的最小堆，放满k个元素；
接下来如果堆顶元素频次小于当前遍历的元素频次就弹出堆顶元素，压入当前元素。最后堆里存放就是前K个高频元素。

算法过程

1. 统计频次：使用哈希表记录数组中每个元素出现的频次，时间复杂度为 $O(n)$（$n$ 为数组长度）。
2. 构建最小堆：将哈希表中的元素（键为元素，值为频次）逐个处理，维护一个容量为 $k$ 的最小堆（堆顶为当前堆中频次最小的元素）：
   • 若堆大小小于 $k$，直接将元素入堆；
   • 若堆大小等于 $k$，且当前元素频次大于堆顶元素频次，则弹出堆顶元素，将当前元素入堆。
   • 每次堆操作（入堆/出堆）的时间复杂度为 $O(\log k)$，需处理 $m$ 个不同元素（$m\le n$），故这一步时间复杂度为 $O(m\log k)$。
3. 提取结果：堆中剩余的 $k$ 个元素即为前 $k$ 个高频元素，提取并返回，时间复杂度为 $O(k)$（可忽略）。

时空复杂度分析

• 时间复杂度：$O(n+m\log k)$，其中 $n$ 是数组长度，$m$ 是不同元素的数量（$m\le n$）。由于 $m\le n$，可简化为 $O(n\log k)$。
• 空间复杂度：$O(m+k)$，哈希表存储 $m$ 个元素（$O(m)$），堆存储 $k$ 个元素（$O(k)$），整体可简化为 $O(n)$（因 $m\le n$）。

代码

/*** @param {number[]} nums* @param {number} k* @return {number[]}*/
var topKFrequent = function(nums, k) {const map = new Map();for (let num of nums) {map.set(num, (map.get(num) || 0) + 1);}const arr = Array.from(map);const priorityQueue = new MyPriorityQueue(k, (a, b) => a[1] - b[1]);for (let a of arr) {if (priorityQueue.size() < k) {priorityQueue.push(a);} else if (priorityQueue.front()[1] < a[1]) {priorityQueue.pop();priorityQueue.push(a);}}const result = [];while (priorityQueue.size() > 0) {let item = priorityQueue.pop();result.push(item[0]);}return result;
};class MyPriorityQueue {constructor(capacity = 1000, compare = (a, b) => a - b) {this._data = [];this._capacity = capacity;this._size = 0;this._compare = compare;}front() {return this._data[0];}push(num) {if (this._capacity === this._size) {this.pop();}this._data.push(num);this.swim();this._size++;}pop() {if (this._data.length === 0) return;[this._data[0], this._data[this._data.length-1]] = [this._data[this._data.length-1], this._data[0]];const item = this._data.pop();this.sink();this._size--;return item;}swim(index = this._data.length-1) {while (index > 0) {let pIndex = Math.floor((index-1)/2);if (this._compare(this._data[index],this._data[pIndex]) < 0) {[this._data[index], this._data[pIndex]] = [this._data[pIndex], this._data[index]];index = pIndex;continue;}break;}}sink(index = 0) {const n = this._data.length;while (true) {let left = 2 * index + 1;let right = left + 1;let biggest = index;if (left < n && this._compare(this._data[left], this._data[index]) < 0) {biggest = left;}if (right < n && this._compare(this._data[right], this._data[biggest]) < 0) {biggest = right;}if (biggest !== index) {[this._data[biggest], this._data[index]] = [this._data[index], this._data[biggest]];index = biggest;continue;}break;}}size() {return this._size;}}

思考二：基于快速排序

该实现利用快速排序的"分区"特性，无需完全排序整个数组，只需找到前 K 个高频元素，大幅提升效率：

1. 首先统计每个元素的出现频率（使用哈希表）
2. 基于频率对元素进行"部分排序"，仅关注前 K 个高频元素
3. 利用快速排序的分区思想，每次分区后判断前 K 个元素是否已找到

算法过程

1. 统计频率：遍历数组，用哈希表记录每个元素的出现次数，时间复杂度 O(n)
2. 构建数组：将哈希表转换为 [元素, 频率] 格式的数组
3. 改进的快速排序：
   • 随机选择基准元素，避免最坏情况
   • 分区时将频率高的元素放在左侧，频率低的放在右侧
   • 分区后检查左侧元素数量：
     • 若左侧元素 >= K，只需递归处理左侧
     • 若左侧元素 < K，记录左侧所有元素，并递归处理右侧剩余所需元素
4. 收集结果：当找到足够的 K 个元素时，直接返回结果

时空复杂度分析

• 时间复杂度：平均 O(n)，最坏 O(n²)

  • 每次分区操作平均可将问题规模减半，总操作次数为 O(n + n/2 + n/4 + …) = O(n)
  • 最坏情况（如元素频率完全有序）下退化为 O(n²)，但随机选择基准可大幅降低此概率

• 空间复杂度：O(n)

  • 哈希表存储频率需要 O(n) 空间
  • 递归调用栈平均 O(log n)，最坏 O(n)

该算法通过避免完全排序，充分利用快速排序的分区特性，在平均情况下达到线性时间复杂度，是解决"前 K 个高频元素"问题的高效方案。

代码

/*** @param {number[]} nums* @param {number} k* @return {number[]}*/
var topKFrequent = function(nums, k) {const map = new Map();for (let num of nums) {map.set(num, (map.get(num) || 0) + 1);}const arr = Array.from(map);const result = Array(k);quickSort(arr, 0, arr.length-1, result, 0, k);    return result;
};function quickSort(arr, start, end, result,  retIndex, k) {let picked =  Math.floor(Math.random() * (end - start + 1)) + start;[arr[picked], arr[start]] = [arr[start], arr[picked]];const pivot = arr[start][1];let index = start;for (let i = start + 1; i <= end; i++) {// 不小于基准值的元素放到左边，小于基准值的元素放到右边if (arr[i][1] >= pivot) {[arr[index + 1], arr[i]] = [arr[i], arr[index + 1]];index++;}}[arr[start], arr[index]] = [arr[index], arr[start]];if (k <= index - start) {quickSort(arr, start, index - 1, result, retIndex, k);} else {for (let i = start; i <= index; i++) {result[retIndex++] = arr[i][0];}if (k > index - start + 1) {quickSort(arr, index + 1, end, result, retIndex, k - (index - start + 1));}}
}

思考三：桶排序

该实现结合“哈希表统计频率”与“桶排序按频率分组”，无需对频率排序，直接通过“从高频桶到低频桶遍历”提取前 K 个元素，充分利用桶排序的“按值分组”特性，实现高效筛选。

算法过程

1. 频率统计：用哈希表遍历数组，记录每个元素的出现次数，同时跟踪最大频率 maxCnt（确定桶的数量）。
2. 桶初始化与分组：创建长度为 maxCnt + 1 的桶数组（索引 = 频率，桶内元素 = 该频率对应的所有元素），将哈希表中的元素按频率放入对应桶中。
3. 提取前 K 高频元素：从最大频率桶（索引 maxCnt）开始，依次向下遍历所有桶，将桶内元素加入结果数组，直到结果数组长度达到 K，直接返回。

时空复杂度分析

代码

/*** @param {number[]} nums* @param {number} k* @return {number[]}*/
var topKFrequent = function(nums, k) {const map = new Map();let maxCnt = 0;for (let num of nums) {map.set(num, (map.get(num) || 0) + 1);maxCnt = Math.max(maxCnt, map.get(num));}const buckets = Array.from({length: maxCnt + 1}, () => []);    for (let [k, cnt] of map) {buckets[cnt].push(k);}const ans = [];for (let i = maxCnt; i >= 0 && ans.length < k; i--) {ans.push(...buckets[i]);}return ans;
};