欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 347. Top K Frequent Elements

程序员文章站 2022-03-07 19:44:49
...

题目

LeetCode 347. Top K Frequent Elements

思路

LeetCode 347. Top K Frequent Elements

  1. 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.
  2. 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.
  3. 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)

代码

LeetCode 347. Top K Frequent Elements

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方法获取其计数.