LeetCode 347. Top K Frequent Elements
程序员文章站
2022-03-07 19:44:49
...
题目
思路
- The first step is to build a hash map. Python provides us both a dictionary structure for the hash map and a method Counter in the collections library to build the hash map we need.This step takes O(N) time where N is number of elements in the list.
- The second step is to build a heap. The time complexity of adding an element in a heap is O(log(k)) and we do it N times that means O(Nlog(k)) time complexity for this step.
- The last step to build an output list has O(klog(k)) time complexity.
In Python there is a method nlargest in heapq library which has the same O(klog(k)) time complexity and combines two last steps in one line.
优先队列也就是最大最小堆。时间复杂度为O(nlogk)
代码
class Solution:
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
count = collections.Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
heapq.nlargest(n, iterable[, key])
从迭代器对象iterable中返回前n个最大的元素列表,其中关键字参数key用于匹配是字典对象的iterable,即选用字典中哪个key作为比较字段。
使用get方法获取其计数.
上一篇: leetcode 414.第三大的数
下一篇: 批处理文件简介与编写第1/2页
推荐阅读
-
LeetCode刷题笔记(Top K Frequent Elements)
-
TOP K frequent-elements
-
C++实现LeetCode(347.前K个高频元素)
-
LeetCode 692. Top K Frequent Words
-
Leetcode 692. Top K Frequent Words
-
692. Top K Frequent Words
-
LeetCode 347: 前 K 个高频元素 Top K Frequent Elements
-
Top K Frequent Elements
-
(Java)leetcode-347 Top K Frequent Elements
-
[Leetcode] Top K Frequent Elements