347. 前 K 个高频元素
思路
1.哈希集合记录每个数字出现的字数
2.s1来记录出现次数对应的数字
如nums =[1,1,1,2,2,3] len(nums)=6 有可能一个数字出现6次的情况
3.s1是记录数字出现0-n次的情况,是有序的,所以从右往左遍历,先遍历到的都是次数最大的
4.s1中会有空的情况 如nums =[1,1,1,2,2,3] ,次数4、5、6都没有,为[],所以用t来存储次数不为空的数字(排好序),t[0:k]即为前K个高频元素
时间复杂度:O(Nlogn)
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
s=dict()
s1=[[] for _ in range(len(nums)+1)]
t=[]
for i in nums:
if i not in s:
s[i]=1
else:
s[i]+=1
for i in s:
s1[s[i]].append(i)
for j in range(len(s1)-1,0,-1):
if s1[j]==[]:
continue
t+=s1[j]
return t[0:k]
原文地址:https://blog.csdn.net/huanxianxianshi/article/details/142756176
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!