柳州公司网站建设,三站一体网站制作,登陆wordpress后台,网站建设与品牌策划方案报价参考题解
题目#xff1a;给定一个数组#xff0c;输出 前k个高频元素。 思路#xff1a; 遍历数组#xff0c;建立小根堆#xff08;小根堆的元素是元组#xff08;num,freq#xff09;#xff0c;排序规则是每个元素的频率#xff09;。 下面使用数组‘heap’…参考题解
题目给定一个数组输出 前k个高频元素。 思路 遍历数组建立小根堆小根堆的元素是元组num,freq排序规则是每个元素的频率。 下面使用数组‘heap’函数’shift_down’,函数‘shift_up’等实现小根堆及其调整上浮、下沉。 def topKFrequent(self, nums: List[int], k: int) - List[int]:def shift_down(arr,root,k):# 下沉的原因是新换了堆顶我们需要为这个堆顶元素找到它在堆中的正确位置# k表示目前堆的有效大小valarr[root] # root node : num,freqwhile root1 k:childroot1if child|1k and arr[child|1][1]arr[child][1]:child|1if arr[child][1]val[1]:arr[root]arr[child]rootchildelse:breakarr[root]valdef shift_up(arr,child):# 上浮调整操作# 上浮原因是我们在堆的末尾添加了新元素我们需要为这个新元素找到它在堆中的正确位置valarr[child]while child1 0 and arr[child1][1]val[1]:arr[child]arr[child1]child1arr[child]valstatcollections.Counter(nums)# 清点数组nums中的元素个数statlist(stat.items())heap[(0,0)] # 用00做垫底为了实现在数组中方便找到父子节点之间的联系如果父节点的索引是root那么左孩子的索引是root1右孩子的索引是(root1)|1。相反地如果孩子的索引是child那么父的索引是child1for i in range(k):heap.append(stat[i])shift_up(heap,len(heap)-1)for i in range(k,len(stat)):if heap[1][1]stat[i][1]:heap[1]stat[i]shift_down(heap,1,k1)return [item[0] for item in heap[1:]]
