力扣347-前K个高频元素

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] 104k的取值范围是[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()