LeetCode0347.K个高频元素前的TopK个频繁元素[Medium][Python][桶排序]ProblemLeetCode给定一个非空整数数组，返回k个最频繁出现的元素。示例1：输入：nums=[1,1,1,2,2,3],k=2输出：[1,2]示例2：输入：nums=[1],k=1输出：[1]注意：您可以假设k始终有效，1≤k≤唯一元素的数量。您的算法的时间复杂度必须优于O(nlogn)，其中n是数组的大小。Problemforce给定一个非空整数数组，返回出现频率最高的前k个元素。示例1：输入：nums=[1,1,1,2,2,3],k=2输出：[1,2]示例2：输入：nums=[1],k=1输出：[1]解释：你可以假设给定的k总是合理的，并且1≤k≤数组中不同元素的数量。您的算法的时间复杂度必须优于O(nlogn)，其中n是数组的大小。思路桶排序首先统计元素的出现频率，相同元素的出现次数+1。然后进行桶排序，将数组中的元素按照出现频率进行分组，即出现频率为的元素我出现在第i个桶中。最后，前k个元素以相反的顺序从桶中移除。时间复杂度：O(n)空间复杂度：O(n)PythoncodeclassSolution(object):deftopKFrequent(self,nums,k):""":typenums:List[int]:typek:int:rtype:List[int]"""#统计元素出现的频率count=dict()fornuminnums:count[num]=count.get(num,0)+1#返回num个元素对应的值dictionarycount，如果没有则赋值为0#Bucket排序bucket=[[]foriinrange(len(nums)+1)]forkey,valueincount.items():bucket[value].append(key)#倒序取出前k个元素res=list()foriinrange(len(nums),-1,-1):#最后一个-1表示倒序ifbucket[i]:res.extend(bucket[i])#in在链表的末尾添加元素iflen(res)>=k:#只有第k个breakreturnres[:k]#输出第k个之前的元素（包括第k个元素）代码地址GitHub链接
