桶排序

题目

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例1：

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例2：

输入: nums = [1], k = 1
输出: [1]

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

题解

桶排序思路：

  • 统计各数出现的频次
  • 以频次为索引建立对应的数的集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def topKFrequent(self, nums, k):# nums:List[int],k:int
        dic =dict()
        for i in nums:
            if i in dic.keys():
                dic[i] +=1
            else:
                dic[i]=1

        new_list= sorted(dic.items(),key=lambda x:x[1])
        tmp=[]
        for i in new_list[-k:]:
            tmp.append(i[0])
        return tmp
1
2
3
4
a = Solution()
nums = [1,1,1,2,2,3]
k = 2
a.topKFrequent(nums,k)
[2, 1]

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2021/03/05/LeetCode-G-%E6%8E%92%E5%BA%8F-347.%20%E5%89%8D%20K%20%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0/