Top K Frequent Elements

这里要求速度高于O(nlgn)，如果用堆来解决的话，这道题的速度可以达到O(klgn)，再次强调，heapify函数没有返回值

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        counter = collections.Counter(nums)
        heap = [(-count, value) for value, count in counter.items()]
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for i in xrange(k)]

这里还有一种利用下标也就是出现次数的桶排序，时间上照道理讲应该是O(n)，但是跑起来速度不如上面这个堆排序的算法

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        counter = collections.Counter(nums)
        n = len(nums)
        bucket = [[] for _ in xrange(n + 1)]
        for key, value in counter.items():
            bucket[value].append(key)

        result = []
        for i in xrange(n, -1, -1):
            while k and bucket[i]:
                result.append(bucket[i].pop())
                k -= 1
            if not k:
                return result

        return result