企业官网建设流程全解析

347. 前 K 个高频元素 - 力扣（LeetCode）

给你一个整数数组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
• -104 <= nums[i] <= 104
• k的取值范围是[1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前k个高频元素的集合是唯一的

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

涉及到频率，显然可以想到哈希表。先用哈希表存储每个元素出现的次数，key 为元素，value 为出现次数。任务变为：将 value 进行排序，取最后 k 个

先考虑一种特殊情况：多个元素出现次数相同。处理办法：将出现次数相同的元素放入一个桶当中，这样无需对桶内元素进行排序

设出现次数的最大值为 max_fre，创建一个大小为 max_fre + 1 的列表 buckets，其中buckets[i]为出现次数为 i 的元素构成的列表。然后遍历哈希表，把元素搬到 buckets 当中

接下来就很简单了，倒序遍历 buckets ，把buckets[i]中的元素加入答案中。当遍历的 bucket 个数为 k 时，返回即可

import sys from typing import List from collections import Counter def solve() -> None: data = sys.stdin.read().strip().split() k = int(data[-1]) nums = list(map(int, data[:-1])) ans = topKFrequent(nums, k) print(" ".join(map(str, ans))) def topKFrequent(nums: List[int], k: int) -> List[int]: # 统计每个元素出现的次数 cnt = Counter(nums) # 记录出现的最大次数 max_fre = max(cnt.values()) # 把出现次数相同的元素，放到同一个桶中 buckets = [[] for _ in range(max_fre + 1)] for element, e_cnt in cnt.items(): buckets[e_cnt].append(element) # 倒序遍历 buckets, 把出现次数前 K 大的元素加入答案 ans = [] for bucket in reversed(buckets): ans += bucket if len(ans) == k: return ans if __name__ == "__main__": solve()