leetcode347-- Top K Frequent Elements

# 小郑之家~

### 题目

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

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.



### 解法


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

for x in nums:
if x not in dic:
dic[x] = 1
else:
dic[x] += 1

ret = sorted(dic.items(), key=lambda x: x[1], reverse=True)

return [x[0] for x in ret[:k]]



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

for x in nums:
if x not in dic:
dic[x] = 1
else:
dic[x] += 1

# 接下来也可以用桶排序，即根据出现的次数，但是同一个次数的可能不止一个，所以要一个二维的

bucket = [[] for _ in range(len(nums))]

for key, value in dic.items():
bucket[value-1].append(key)

# get the bucket 次数最多的在后面
ret = []

for i in range(len(nums)-1, -1,-1):
ret += bucket[i]
if len(ret) >= k:
break

return ret[:k]