Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,

Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

• 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.

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        dict = {}
        for n in nums:
            dict[n] = dict.get(n,0) + 1
        v = list(reversed(sorted([value for key,value in dict.items()])))
        return [key for key,value in dict.items() if value in v[:k]]

Python2.7+之后的版本，在 collections 库裡有一种类 Counter 可以用。

详细的操作方法请参考Counter object

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        from collections import Counter
        counter = Counter(nums).most_common(k)
        return [key for key, count in counter]