leetcode

Top K Frequent Elements

Top K Frequent Elements

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.

  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        ret = {}
        res = []
        for x in nums:  # O(n)
            if x not in ret:
                ret[x] = 1
            else:
                ret[x] += 1
        for key, value in sorted(ret.iteritems(), key=lambda (k,v): (v,k), reverse=True)[:k]:  # O(n log n)
            res.append(key)
        return res

O(n) + O(n log n) = O(n log n)

result

1
2
3
4
5
6
7
8
In [221]: nums = [1,1,1,2,2,3]
In [222]: k = 2
In [241]: s = Solution()
In [242]: s.topKFrequent(nums, k)
Out[242]: [1, 2]

How to sort a Python dict (dictionary) by keys or values

『Python CoolBook：heapq』数据结构和算法_heapq堆队列算法&容器排序

Python使用heapq实现小顶堆（TopK大）、大顶堆（BtmK小）

使用heapq构建最小堆和最大堆

leet code