【leetcode100】前K个高频元素

1、题目形貌

给你一个整数数组 nums 和一个整数 k ，请你返回此中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:

1. <strong>输入: </strong>nums = [1,1,1,2,2,3], k = 2
2. <strong>输出: </strong>[1,2]

复制代码

示例 2:

1. <strong>输入: </strong>nums = [1], k = 1
2. <strong>输出: </strong>[1]

复制代码

2、初始思绪

2.1 思绪

全分列，起首使用字典存储每个数字出现的次数，然后对字典按照出现次数进行排序后输出。
2.2 完备代码

1. class Solution:
2.     def topKFrequent(self, nums: List[int], k: int) -> List[int]:
3.         dic = {}
4.         for num in nums:
5.             if num in dic.keys():
6.                 dic[num] += 1
7.             else:
8.                 dic[num] = 1
9.         #print(dic)
10.         dic = sorted(dic.items(), key = lambda x:x[1], reverse = True)
11.         #print(dic)
12.         ans = []
13.         for i in range(k):
14.             ans.append(dic[i][0])
15.         return ans

复制代码

2.3 注意点！

（1）时间复杂度为O(nlog n)，不满足题目中要求你所设计算法的时间复杂度 必须 优于 O(n log n) ，此中 n 是数组大小。
（2）对字典存储数字出现次数把握不熟练，可以简化代码：

1. dic = Counter(nums)

复制代码

3 优化算法1

3.1 思绪

使用堆的前K个元素的思绪进行求解，时间复杂度为O(nlog k)。
3.2 代码

1. class Solution:
2.     def topKFrequent(self, nums: List[int], k: int) -> List[int]:
3.         heap = []
4.         dic = Counter(nums)
5.         for num, count in dic.items():
6.             heapq.heappush(heap, (count, num))
7.             if len(heap) > k:
8.                 heapq.heappop(heap)
9.         return [heap[i][1] for i in range(len(heap))]

复制代码

 3.3 增补知识

为更好地使用堆，本文对堆进行了整理，具体如下：

 

4 优化算法2

4.1 思绪

使用heapq的函数heapq.nlargerst，时间复杂度为O(nlog k)。
4.2 代码

1. class Solution:
2.     def topKFrequent(self, nums: List[int], k: int) -> List[int]:
3.         dic = Counter(nums)
4.         res = heapq.nlargest(k, dic.items(), key = lambda x:x[1])
5.         return [res[i][0] for i in range(k)]

复制代码

 4.3 增补知识

heapq.nlargest(n, iterable) 用于从可迭代对象（如列表、元组等）中提取 前 n 个最大元素，返回一个包罗这些元素的列表（按从大到小分列）。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。