LeetCode--347. 前 K 个高频元素/Golang中的堆(container/heap)
例题链接-前k个高频元素
前言
以前都是用的C++写算法题,最近也想熟悉一下golang的数据结构,故来一篇题解+堆分析。
正文
这里重点不在分析题目,在于golang中的 container/heap
对于内部实现逻辑有兴趣的可以去看看源码。
这里先给出题解的代码
package mainimport ("container/heap""fmt"
)// IHeap 是一个最小堆的实现
type IHeap [][2]intfunc (h IHeap) Len() int {return len(h)
}func (h IHeap) Less(i, j int) bool {return h[i][1] < h[j][1]
}
func (h IHeap) Swap(i, j int) {h[i], h[j] = h[j], h[i]
}// Push 方法将元素添加到堆中
func (h *IHeap) Push(x interface{}) {*h = append(*h, x.([2]int))
}// Pop 方法移除并返回堆顶元素
func (h *IHeap) Pop() interface{} {old := *hn := len(old)x := old[n-1]*h = old[0 : n-1]return x
}// topKFrequent 函数找到数组中出现频率最高的 k 个元素
func topKFrequent(nums []int, k int) []int {// 统计每个数字的出现频率m := map[int]int{}for _, num := range nums {m[num]++}// 创建最小堆h := &IHeap{}heap.Init(h)// 将元素推入堆并维护堆的大小for key, value := range m {heap.Push(h, [2]int{key, value})if h.Len() > k {heap.Pop(h)}}// 从堆中提取结果ret := make([]int, k)for i := 0; i < k; i++ {ret[k-i-1] = heap.Pop(h).([2]int)[0]}return ret
}func main() {nums := []int{1, 1, 216, 216, 216, 216, 216, 216, 6, 1, 2, 2, 3, 9, 9, 5, 6, 0, 6, 6, 9, 4, 5, 12, 6, 459, 15, 15, 216, 26, 15, 115, 15}k := 5fmt.Println(topKFrequent(nums, k))
}
1. 结构定义
这部分定义了我们的堆中元素的基本结构,每个元素有两部分组成,这也令go中的堆的元素更加灵活,可以支持很多数据结构。
type IHeap [][2]int
2. Len()方法
首先,需要实现我们的Len方法,实现这个方法的目的是,他将会在之后函数内部的Down/Up方法所调用,具有重要的作用(这部分在源码里面)
func (h IHeap) Len() int {return len(h)
}
3. Less()方法
Less方法的定义主要是实现了堆内部的比较器,也就是排序原则,就是大根堆和小根堆的区别
func (h IHeap) Less(i, j int) bool {return h[i][1] < h[j][1]
}
4. Swap()方法
这部分也是主要用于Down和Up内部调用,表示利用传入的下标来进行元素位置的交换
func (h IHeap) Swap(i, j int) {h[i], h[j] = h[j], h[i]
}
5. Push()方法
push方法也是用于内部的push函数的调用,此处不需要进行Down或者Up的操作,因为内部的Push函数已经为你准备好了。
func (h *IHeap) Push(x interface{}) {*h = append(*h, x.([2]int))
}
6. Pop()方法
移除堆顶元素的方法,同样用于内部调用
func (h *IHeap) Pop() interface{} {old := *hn := len(old)x := old[n-1]*h = old[0 : n-1]return x
}
结语
以上提到方法都需要我们自己定义一个堆,并实现Heap的接口,才能对heap的函数进行调用,从而实现堆的效果。
总的来说,go的堆虽然实现比较繁琐,但是管理起来却比较灵活,其实比起c++里面的stl,go里面的container/heap让我更有写的欲望吧…😋
相关文章:
LeetCode--347. 前 K 个高频元素/Golang中的堆(container/heap)
例题链接-前k个高频元素 前言 以前都是用的C写算法题,最近也想熟悉一下golang的数据结构,故来一篇题解堆分析。 正文 这里重点不在分析题目,在于golang中的 container/heap 对于内部实现逻辑有兴趣的可以去看看源码。 这里先给出题解的代…...
关于大数据
在大数据背景下存在的问题: 非结构化、半结构化数据:NoSQL数据库只负责存储;程序处理时涉及到数据移动,速度慢 是否存在一套整体解决方案? 可以存储并处理海量结构化、半结构化、非结构化数据 处理海量数据的速…...
9-收纳的知识
[ComponentOf(typeof(xxx))]组件描述,表示是哪个实体的组件 [EntitySystemOf(typeof(xxx))] 系统描述 [Event(SceneType.Demo)] 定义事件,在指定场景的指定事件发生后触发 [ChildOf(typeof(ComputersComponent))] 标明是谁的子实体 [ResponseType(na…...
堆的实现——堆的应用(堆排序)
文章目录 1.堆的实现2.堆的应用--堆排序 大家在学堆的时候,需要有二叉树的基础知识,大家可以看我的二叉树文章:二叉树 1.堆的实现 如果有⼀个关键码的集合 K {k0 , k1 , k2 , …,kn−1 } ,把它的所有元素按完全⼆叉树…...
机器学习6-全连接神经网络2
机器学习6-全连接神经网络2-梯度算法改进 梯度下降算法存在的问题动量法与自适应梯度动量法一、动量法的核心思想二、动量法的数学表示三、动量法的作用四、动量法的应用五、示例 自适应梯度与RMSProp 权值初始化随机权值初始化Xavier初始化HE初始化(MSRA) ![在这里插入图片描述…...
基于 SpringBoot 的电影购票系统
基于SpringBoot的电影购票系统是一个集成了现代化Web开发技术的在线电影票务平台。以下是对该系统的详细介绍: 一、系统背景与意义 随着电影行业的快速发展和观众对观影体验的不断追求,电影票务管理面临着越来越多的挑战。传统的票务管理方式存在效率低…...
C++SLT(三)——list
目录 一、list的介绍二、list的使用list的定义方式 三、list的插入和删除push_back和pop_backpush_front和pop_frontinserterase 四、list的迭代器使用五、list的元素获取六、list的大小控制七、list的操作函数sort和reversemergeremoveremove_ifuniqueassignswap 一、list的介…...
C++ Primer 算术运算符
欢迎阅读我的 【CPrimer】专栏 专栏简介:本专栏主要面向C初学者,解释C的一些基本概念和基础语言特性,涉及C标准库的用法,面向对象特性,泛型特性高级用法。通过使用标准库中定义的抽象设施,使你更加适应高级…...
数据结构-堆和PriorityQueue
1.堆(Heap) 1.1堆的概念 堆是一种非常重要的数据结构,通常被实现为一种特殊的完全二叉树 如果有一个关键码的集合K{k0,k1,k2,...,kn-1},把它所有的元素按照完全二叉树的顺序存储在一个一维数组中,如果满足ki<k2i…...
【玩转 Postman 接口测试与开发2_017】第13章:在 Postman 中实现契约测试(Contract Testing)与 API 接口验证(下)
《API Testing and Development with Postman》最新第二版封面 文章目录 第十三章 契约测试与 API 接口验证8 导入官方契约测试集合9 契约测试集合的详细配置9.1 env-apiKey 的创建与设置9.2 env-workspaceId 的设置9.3 Mock 服务器及 env-server 的配置9.4 API 测试实例的配置…...
R语言 | 使用 ComplexHeatmap 绘制热图,分区并给对角线分区加黑边框
目的:画热图,分区,给对角线分区添加黑色边框 建议直接看0和4。 0. 准备数据 # 安装并加载必要的包 #install.packages("ComplexHeatmap") # 如果尚未安装 library(ComplexHeatmap)# 使用 iris 数据集 #data(iris)# 选择数值列&a…...
React图标库: 使用React Icons实现定制化图标效果
React图标库: 使用React Icons实现定制化图标效果 图标库介绍 是一个专门为React应用设计的图标库,它包含了丰富的图标集合,覆盖了常用的图标类型,如FontAwesome、Material Design等。React Icons可以让开发者在React应用中轻松地添加、定制各…...
Python sider-ai-api库 — 访问Claude、llama、ChatGPT、gemini、o1等大模型API
目前国内少有调用ChatGPT、Claude、Gemini等国外大模型API的库。 Python库sider_ai_api 提供了调用这些大模型的一个完整解决方案, 使得开发者能调用 sider.ai 的API,实现大模型的访问。 Sider是谷歌浏览器和Edge的插件,能调用ChatGPT、Clau…...
DeepSeek、哪吒和数据库:厚积薄发的力量
以下有部分来源于AI,毕竟我认为AI还不能替代,他只能是辅助 快速迭代是应用程序不是工程 在这个追求快速迭代、小步快跑的时代,我们似乎总是被 “快” 的节奏裹挟着前进。但当我们静下心来,审视 DeepSeek 的发展、饺子导演创作哪吒…...
DDD - 微服务架构模型_领域驱动设计(DDD)分层架构 vs 整洁架构(洋葱架构) vs 六边形架构(端口-适配器架构)
文章目录 引言1. 概述2. 领域驱动设计(DDD)分层架构模型2.1 DDD的核心概念2.2 DDD架构分层解析 3. 整洁架构:洋葱架构与依赖倒置3.1 整洁架构的核心思想3.2 整洁架构的层次结构 4. 六边形架构:解耦核心业务与外部系统4.1 六边形架…...
第 1 天:UE5 C++ 开发环境搭建,全流程指南
🎯 目标:搭建 Unreal Engine 5(UE5)C 开发环境,配置 Visual Studio 并成功运行 C 代码! 1️⃣ Unreal Engine 5 安装 🔹 下载与安装 Unreal Engine 5 步骤: 注册并安装 Epic Game…...
【华为OD-E卷 - 109 磁盘容量排序 100分(python、java、c++、js、c)】
【华为OD-E卷 - 磁盘容量排序 100分(python、java、c、js、c)】 题目 磁盘的容量单位常用的有M,G,T这三个等级, 它们之间的换算关系为1T 1024G,1G 1024M, 现在给定n块磁盘的容量,…...
【大数据技术】编写Python代码实现词频统计(python+hadoop+mapreduce+yarn)
编写Python代码实现词频统计(python+hadoop+mapreduce+yarn) 搭建完全分布式高可用大数据集群(VMware+CentOS+FinalShell) 搭建完全分布式高可用大数据集群(Hadoop+MapReduce+Yarn) 本机PyCharm连接CentOS虚拟机 在阅读本文前,请确保已经阅读过以上三篇文章,成功搭建了…...
5-Scene层级关系
Fiber里有个scene是只读属性,能从fiber中获取它属于哪个场景,scene实体中又声明了fiber,fiber与scene是互相引用的关系。 scene层级关系 举例 在unity.core中的EntityHelper中,可以通过entity获取对应的scene root fiber等属性…...
JVM执行流程与架构(对应不同版本JDK)
直接上图(对应JDK8以及以后的HotSpot) 这里主要区分说明一下 方法区于 字符串常量池 的位置更迭: 方法区 JDK7 以及之前的版本将方法区存放在堆区域中的 永久代空间,堆的大小由虚拟机参数来控制。 JDK8 以及之后的版本将方法…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
