力扣刷题Python笔记：前 K 个高频元素
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了力扣刷题Python笔记：前 K 个高频元素，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2653字，纯文字阅读大概需要4分钟。
内容图文
题目
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
提示：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
来源：力扣（LeetCode）
Python解法
二叉堆与优先队列
这道题用到了二叉堆与优先队列的相关知识点。
二叉树本质是一种完全二叉树，它分为最大堆和最小堆。最大堆的任何一个父节点，都大于等于它的左子节点或右子节点的值。最小堆的任何一个父节点，都小于等于它的左子节点或右子节点的值。二叉堆的根节点叫作堆顶，最大堆的堆顶是整个堆中的最大元素，最小堆的堆顶是整个堆中的最小元素。
队列的特点是先进先出（FIFO）。而优先队列不再遵循先入先出的规则，而是分为两类：最大优先队列和最小优先队列。最大优先队列是无论入队顺序如何，都是当前最大的元素优先出队。最小优先队列是无论入队顺序如何，都是当前最小的元素优先出队。
因此，我们可以结合以上两部分知识来解决这道题。具体思路如下：
- 根据给定数组计算每个元素的个数并将其转换成列表的形式 stat，列表 stat 中的元素形式为 (某一种元素, 元素个数)；
- 因为最小堆是一种完全二叉树，我们假设完全二叉树是从索引 1 开始计算的，因此对于索引 i，它的左子节点索引是 2i，右子节点索引是 2i+1；
- 创建最小堆 heap，在最开始插入一个占位节点 (0, 0)，此时最小堆堆顶索引与数组 heap 索引为 1 的位置相同；
- 读取 stat 中前 k 个元素，将其逐个放入数组 heap 中并利用上浮方法进行排序，最终二叉堆的规模为 k+1，多出来的1 为占位节点；
- 依次读取 stat 中除前 k 个元素外剩下的元素，并判断该元素对应的元素个数是否大于二叉堆的堆顶，即是否 heap[1]；
- 如果大于，说明相比于 heap[1] 该元素更满足要求，将堆顶用该元素替换，然后将该元素逐渐下沉到它应在的位置；
- 最后，排除占位节点输出 heap[1:] 即为所求结果。
代码如下：
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
def sift_down(arr, root, k):
"""下沉log(k),如果新的根节点>子节点就一直下沉"""
val = arr[root] # 用类似插入排序的赋值交换
while root<<1 < k:
child = root << 1
# 选取左右孩子中小的与父节点交换
if child|1 < k and arr[child|1][1] < arr[child][1]:
child |= 1
# 如果子节点<新节点,交换,如果已经有序break
if arr[child][1] < val[1]:
arr[root] = arr[child]
root = child
else:
break
arr[root] = val
def sift_up(arr, child):
"""上浮log(k),如果新加入的节点<父节点就一直上浮"""
val = arr[child]
while child>>1 > 0 and val[1] < arr[child>>1][1]:
arr[child] = arr[child>>1]
child >>= 1
arr[child] = val
stat = collections.Counter(nums)
stat = list(stat.items())
heap = [(0,0)]
# 构建规模为k+1的堆,新元素加入堆尾,上浮
for i in range(k):
heap.append(stat[i])
sift_up(heap, len(heap)-1)
# 维护规模为k+1的堆,如果新元素大于堆顶,入堆,并下沉
for i in range(k, len(stat)):
if stat[i][1] > heap[1][1]:
heap[1] = stat[i]
sift_down(heap, 1, k+1)
return [item[0] for item in heap[1:]]
内容总结
以上是互联网集市为您收集整理的力扣刷题Python笔记：前 K 个高频元素全部内容，希望文章能够帮你解决力扣刷题Python笔记：前 K 个高频元素所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。