## 题目描述：

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总是有效的，1 ≤ k ≤ 独立元素的个数。
• 你的算法时间复杂度必须优于O(n log n)，其中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]
``````

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

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)]
``````

Pingbacks已关闭。