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 高的元素。你可以按 任意顺序 返回答案。

解题思路

可以使用哈希映射和小顶堆来实现：

1. 使用哈希映射存储数组中每个元素的频率。
2. 创建一个小顶堆（优先队列），用于跟踪出现频率最高的 k 个元素。
3. 遍历哈希映射，将元素和其频率添加到小顶堆中，拿它与堆顶的元素对比。
   • 如果比堆顶元素大，就把堆顶元素删除，并且将这个元素插入到堆中；
   • 如果比堆顶元素小，则不做处理；
4. 处理完所有元素后，小顶堆中将包含 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	链表频率 🔒		哈希表 链表 计数