347. Top K Frequent Elements
347. Top K Frequent Elements
🟠 🔖 数组
哈希表
分治
桶排序
计数
快速选择
排序
堆(优先队列)
🔗 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. 统计词频](https://leetcode.com/problems/word-frequency)
- [215. 数组中的第 K 个最大元素](https://leetcode.com/problems/kth-largest-element-in-an-array)
- [451. 根据字符出现频率排序](https://leetcode.com/problems/sort-characters-by-frequency)
- [659. 分割数组为连续子序列](https://leetcode.com/problems/split-array-into-consecutive-subsequences)
- [692. 前 K 个高频单词](https://leetcode.com/problems/top-k-frequent-words)
- [973. 最接近原点的 K 个点](https://leetcode.com/problems/k-closest-points-to-origin)
- [🔒 Sort Features by Popularity](https://leetcode.com/problems/sort-features-by-popularity)
- [2284. 最多单词数的发件人](https://leetcode.com/problems/sender-with-largest-word-count)
- [2404. 出现最频繁的偶数元素](https://leetcode.com/problems/most-frequent-even-element)