千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

导航： 首页 > 互联网科技 >

golang中怎么利用leetcode 求最小的k个数

发表于：2025-12-02 作者：千家信息网编辑
千家信息网最后更新 2025年12月02日，本篇文章为大家展示了golang中怎么利用leetcode 求最小的k个数，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。输入整数数组 arr ，找出其中最小的
千家信息网最后更新 2025年12月02日golang中怎么利用leetcode 求最小的k个数

本篇文章为大家展示了golang中怎么利用leetcode 求最小的k个数，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2

输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1

输出：[0]

限制：

0 <= k <= arr.length <= 10000

0 <= arr[i] <= 10000

解题思路

1，本题其实就是实现大根堆

2，堆的性质：

A，堆逻辑上是一棵完全二叉树，实现上是一个数组

B，对于节点i，左孩子是2*i+1 ，右孩子是 2*i+2，父亲节点是 (i-1)/2

3，未达到堆容量时，需要建堆。把元素加到数组末尾，然后调整堆：

如果当前节点值比父亲节点值大，交换元素，然后递归调整父亲节点

4，达到堆容量后，比较元素和堆顶元素大小，如果比堆顶元素小，替换堆顶元素，然后调整堆：

和左右孩子中较大者交换，然后递归调整堆。

代码实现

func getLeastNumbers(arr []int, k int) []int {   if k<1{       return []int{}   }   if len(arr)<=k{       return arr   }
   h:=heap{cap:k}   for i:=0;i       h.data=append(h.data,arr[i])      h.build(i)   }   for i:=k;i       if arr[i]           h.data[0]= arr[i]          h.heaplify(0)       }   }   return h.get()}

type heap struct{    cap int    data []int}
func(this*heap)heaplify(i int){   l:=2*i+1   r:=2*i+2   if l>=this.cap{       return   }
   if r>=this.cap{       if this.data[l]>this.data[i]{           this.data[l],this.data[i]=this.data[i],this.data[l]       }       return    }   if this.data[l]>this.data[r]{       if this.data[l]>this.data[i]{           this.data[l],this.data[i]=this.data[i],this.data[l]           this.heaplify(l)       }   }else{        if this.data[r]>this.data[i]{           this.data[r],this.data[i]=this.data[i],this.data[r]           this.heaplify(r)        }   }}
func (this*heap)build(i int){     p:=(i-1)/2     if p>=0 && this.data[p]        this.data[p],this.data[i]=this.data[i],this.data[p]        this.build(p)     }}



func(this*heap)get()[]int{    return this.data}

上述内容就是golang中怎么利用leetcode 求最小的k个数，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注行业资讯频道。

很赞哦！
元素 节点 最小 调整 输入 个数 孩子 数组 父亲 内容 容量 就是 技能 数字 知识 示例 递归 输出 简明 较大 数据库的安全要保护哪些东西 数据库安全各自的含义是什么 生产安全数据库录入 数据库的安全性及管理 数据库安全策略包含哪些 海淀数据库安全审计系统 建立农村房屋安全信息数据库 易用的数据库客户端支持安全管理 连接数据库失败ssl安全错误 数据库的锁怎样保障安全 金山区品牌软件开发定制要求 维护网络安全开头 厦门装舒易网络技术有限公司 大专学网络技术出来找什么工作 山东手机软件开发报价 辽宁软件开发技术服务价格 服务器调试和安装有发展空间吗 软件开发公司会计准则 上海机旁备件管理软件开发 上海人脸化妆软件开发 上海软件开发代理会计记账 r 语言 数据库 酷狗直播用什么软件开发的 华为v5服务器升级bios 网络安全青少年大赛 上证50etf期权软件开发 网络安全民警法规 广告推广软件开发项目 服务器外网 上海常见网络技术价格走势 大专自学数据库好找人吗 皮肤管理 服务器 shell脚本备份数据库 宝塔数据库删不掉是怎么回事 网络安全市场大吗 ios如何查看数据库文件 上海参考软件开发定制收费 数据库并发一致性 浦东新区常见软件开发参考价格 数据分析和数据库设计

相关文章

0