|
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法一：字典排序
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
dict = {}
for i in nums:
if i not in dict:
dict[i] = 1
else:
dict[i] += 1
print('dict1:')
print(dict)
dict_sort = sorted(dict.items(), key = lambda x: x[1],reverse = True)
print('sorted dict:')
print(dict_sort)
res = []
for i in range(k):
res.append(dict_sort[i][0])
return res
解法二：桶排序
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
maps = {}
#生成字典映射
for i in nums:
# print('i:%d,maps.get(i,0):%d' %(i, maps.get(i,0)))
maps[i] = maps.get(i,0) + 1
max_time = max(maps.values())
print(maps)
#根据最大次数生成桶
TongList = [[] for i in range(max_time+1)]
for key ,value in maps.items():
TongList[value].append(key)
print(TongList)
res = []
for i in range(max_time, 0, -1):
print('i:%d' %(i))
if TongList[i]:
res.extend(TongList[i])
if len(res) >= k:
return res[:k]
| 
转播
