题目描述:
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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。