Top K Frequent Elements

这道题属于传统的K类问题，这里是求出现的数字元素的频率问题，也可以推向找字符串的词频，原理也是一样的，很显然这道题是可以用堆和哈希表来对词频进行统计排序从而达到一个O(nlgk)的时间复杂度的，这种做法就是一般的top k类做法，这里不详细讲了，这道题还可以用桶排序的思路实现一个O(n+k)的时间复杂度解法，如果熟悉计数排序之类的非比较算法，这种思路的实现也是没有什么难度的，这里写下自己的代码，不是很干净但是考虑了一些边界情况，比LeetCode赞数最高的Java代码要robust

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        n = len(nums)

        freqMap = {}
        bucket = [set([]) for _ in xrange(n + 1)]          # 需要set是因为有可能有高频词，我们只需要记录一次就够了

        for num in nums:
            if num in freqMap:
                freqMap[num] += 1
            else:
                freqMap[num] = 1

        for num in nums:
            bucket[freqMap[num]].add(num)                  

        res = []
        for i in xrange(n , -1, -1):
            if bucket[i]:
                for ent in bucket[i]:      # 这里对每一个有词的桶必须逐个清扫，因为当前的k有可能不足以拿完这个桶里面的词
                    if k == 0:
                        break
                    res.append(ent)
                    k -= 1
            if k == 0:
                return res

        return res