千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

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

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

发表于：2025-01-27 作者：千家信息网编辑
千家信息网最后更新 2025年01月27日，本篇文章为大家展示了golang中怎么利用leetcode 求最小的k个数，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。输入整数数组 arr ，找出其中最小的
千家信息网最后更新 2025年01月27日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安全错误 数据库的锁怎样保障安全 mssql数据库备份 忍者必须死3更换服务器 怎么显示微信无法连接服务器 it跑数据库 钉钉 设备管理软件开发 t6系统管理在服务器上吗 软件开发用笔记本电脑选择 数据库应用平台搭建实验常见问题 软件开发适用笔记本 锦江区海鑫软件开发工作室 福建信息化软件开发价格大全 会计数据年鉴数据库 无忧借条软件开发 计算机软件开发 是 什么网站适合独立服务器 河北张北网络安全 反应动力学数据库 关系型数据库建表格式 张家口软件开发联系方式 网络安全与执法找工作 网络安全审计终端厂家 方舟手游进服送100级服务器推荐 计算机网络技术静态改动态 vpa服务器怎么用 家居设计软件开发公司 华为河图数据库是啥 化工计算机网络技术 表格类软件开发平台 三十处第三届网络安全知识竞赛 多平台文件服务器

相关文章

0