赞
踩
class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: # 构造hash dic = {} for i in nums: dic[i] = dic.get(i, 0)+1 self.res = [] for i in dic: self.res.append([dic[i], i]) # 构造大顶堆 for i in range(len(self.res)//2, -1, -1): self.max_heap(i, len(self.res)) # 堆排序 ans = [] for j in range(len(self.res)-1, len(self.res)-k-1, -1): ans.append(self.res[0][1]) self.res[0], self.res[j] = self.res[j], self.res[0] self.max_heap(0, j) return ans def max_heap(self, i, n): j = i*2+1 while j < n: if j+1 < n and self.res[j+1][0] > self.res[j][0]: j += 1 if self.res[j][0] > self.res[i][0]: self.res[j], self.res[i] = self.res[i], self.res[j] i = j j = i*2+1 else: break
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。