347. 前 K 个高频元素
347. 前 K 个高频元素
🟠 🔖 数组
哈希表
分治
桶排序
计数
快速选择
排序
堆(优先队列)
🔗 力扣
LeetCode
题目
Given an integer array nums
and an integer k
, return the k
most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
k
is in the range[1, the number of unique elements in the array]
.- It is guaranteed that the answer is unique.
Follow up: Your algorithm's time complexity must be better than O(n log n)
, where n is the array's size.
题目大意
给你一个整数数组 nums
和一个整数 k
,请你返回其中出现频率前 k
高的元素。你可以按 任意顺序 返回答案。
解题思路
可以使用哈希映射和小顶堆来实现:
- 使用哈希映射存储数组中每个元素的频率。
- 创建一个小顶堆(优先队列),用于跟踪出现频率最高的
k
个元素。 - 遍历哈希映射,将元素和其频率添加到小顶堆中,拿它与堆顶的元素对比。
- 如果比堆顶元素大,就把堆顶元素删除,并且将这个元素插入到堆中;
- 如果比堆顶元素小,则不做处理;
- 处理完所有元素后,小顶堆中将包含
k
个最高频率的元素。
复杂度分析
- 时间复杂度:
O(n log k)
,其中n
是数组的大小,k
是唯一元素的数量,相较于传统排序算法的O(n log n)
更为高效。 - 空间复杂度:
O(k)
,需要额外的空间来存储堆。
代码
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function (nums, k) {
let map = new Map();
for (let i of nums) {
map.set(i, map.has(i) ? map.get(i) + 1 : 1);
}
let heap = [];
const add = ([val, freq]) => {
if (heap.length < k) {
heap.push([val, freq]);
heapifyUp(heap.length - 1);
} else if (heap[0][1] < freq) {
heap[0] = [val, freq];
heapifyDown(0);
}
};
const heapifyUp = (i) => {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (heap[i][1] < heap[parent][1]) {
[heap[parent], heap[i]] = [heap[i], heap[parent]];
i = parent;
} else {
break;
}
}
};
const heapifyDown = (i) => {
const left = 2 * i + 1;
const right = 2 * i + 2;
let min = i;
if (left < heap.length && heap[left][1] < heap[min][1]) {
min = left;
}
if (right < heap.length && heap[right][1] < heap[min][1]) {
min = right;
}
if (min !== i) {
[heap[i], heap[min]] = [heap[min], heap[i]];
heapifyDown(min);
}
};
for (item of map.entries()) {
add(item);
}
return heap.map((i) => i[0]);
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
192 | 统计词频 | Shell | 🟠 | 🀄️ 🔗 | |
215 | 数组中的第K个最大元素 | [✓] | 数组 分治 快速选择 2+ | 🟠 | 🀄️ 🔗 |
451 | 根据字符出现频率排序 | [✓] | 哈希表 字符串 桶排序 3+ | 🟠 | 🀄️ 🔗 |
659 | 分割数组为连续子序列 | 贪心 数组 哈希表 1+ | 🟠 | 🀄️ 🔗 | |
692 | 前K个高频单词 | 字典树 哈希表 字符串 4+ | 🟠 | 🀄️ 🔗 | |
973 | 最接近原点的 K 个点 | [✓] | 几何 数组 数学 4+ | 🟠 | 🀄️ 🔗 |
1772 | 按受欢迎程度排列功能 🔒 | 数组 哈希表 字符串 1+ | 🟠 | 🀄️ 🔗 | |
2284 | 最多单词数的发件人 | 数组 哈希表 字符串 1+ | 🟠 | 🀄️ 🔗 | |
2404 | 出现最频繁的偶数元素 | 数组 哈希表 计数 | 🟢 | 🀄️ 🔗 | |
3063 | 链表频率 🔒 | 哈希表 链表 计数 | 🟢 | 🀄️ 🔗 |