leetcode_347. 前 K 个高频元素
【摘要】 目录
一、题目要求
二、解题思路
三、代码
一、题目要求
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
...
目录
一、题目要求
给定一个非空的整数数组，返回其中出现频率前 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.用dict存储数字对应的个数
2.按照value即出现次数排序
3.用list存储排序之后的dict的key值
4.取list中前k个数
三、代码
-
class Solution:
-
def topKFrequent(self, nums, k: int):
-
res = []
-
num_count_dict = {}
-
for num in nums:
-
if num in num_count_dict:
-
num_count_dict[num] += 1
-
else:
-
num_count_dict[num] = 1
-
sorted_num_count_dict = sorted(num_count_dict.items(),
-
key=lambda x: x[1],
-
reverse=True)
-
for (num, count) in sorted_num_count_dict:
-
res.append(num)
-
if k <= len(res):
-
return res[:k]
-
else:
-
return res
-
-
-
if __name__ == '__main__':
-
nums = [1,1,1,2,2,3]
-
k = 2
-
-
s = Solution()
-
ans = s.topKFrequent(nums, k)
-
print(ans)
-
文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。
原文链接：nickhuang1996.blog.csdn.net/article/details/108441840
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）