题目描述：

LeetCode 347. 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.

题目大意：

给定一个非空整数数组，返回其前k个出现次数最多的元素。

测试用例如题目描述。

注意：

• 你可以假设k总是有效的，1 ≤ k ≤ 独立元素的个数。
• 你的算法时间复杂度必须优于O(n log n)，其中n是数组的长度。

解题思路：

解法I 桶排序（Bucket Sort） 时间复杂度O(n)

1. 遍历数组nums，利用字典cntDict统计各元素出现次数。
2. 遍历cntDict，利用嵌套列表freqList记录出现次数为i（ i∈[1, n] ）的所有元素
3. 逆序遍历freqList，将其中的前k个元素输出。

Python代码：

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        n = len(nums)
        cntDict = collections.defaultdict(int)
        for i in nums:
            cntDict[i] += 1
        freqList = [[] for i in range(n + 1)]
        for p in cntDict:
            freqList[cntDict[p]] += p,
        ans = []
        for p in range(n, 0, -1):
            ans += freqList[p]
        return ans[:k]

解法II 哈希表 + 堆 时间复杂度O(n * log k)，其中k为独立元素的个数。

使用collections.Counter的most_common方法，可以使代码简化。

实际上，most_common的实现应用了heapq（堆）模块。

参阅Counter的源代码：

https://hg.python.org/cpython/file/2.7/Lib/collections.py

以及heapq的源代码：

https://hg.python.org/cpython/file/2.7/Lib/heapq.py

Python代码：

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        c = collections.Counter(nums)
        return [x[0] for x in c.most_common(k)]

 

本文链接：http://bookshadow.com/weblog/2016/05/02/leetcode-top-k-frequent-elements/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码