【Leetcode 347】,前k个高频元素,小根堆的调整
参考题解
题目:给定一个数组,输出 前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表示目前堆的有效大小val=arr[root] # root node : <num,freq>while root<<1 <k:child=root<<1if child|1<k and arr[child|1][1]<arr[child][1]:child|=1if arr[child][1]<val[1]:arr[root]=arr[child]root=childelse:breakarr[root]=valdef shift_up(arr,child):# 上浮调整操作,# 上浮原因是,我们在堆的末尾添加了新元素,我们需要为这个新元素找到它在堆中的正确位置val=arr[child]while child>>1 >0 and arr[child>>1][1]>val[1]:arr[child]=arr[child>>1]child>>=1arr[child]=valstat=collections.Counter(nums)# 清点数组nums中的元素个数stat=list(stat.items())heap=[(0,0)] # 用(0,0)做垫底,为了实现在数组中方便找到父子节点之间的联系,如果父节点的索引是root,那么左孩子的索引是root<<1,右孩子的索引是(root<<1)|1。相反地,如果孩子的索引是child,那么父的索引是child>>1for 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,k+1)return [item[0] for item in heap[1:]]
相关文章:
【Leetcode 347】,前k个高频元素,小根堆的调整
参考题解 题目:给定一个数组,输出 前k个高频元素。 思路: 遍历数组,建立小根堆(小根堆的元素是元组(num,freq),排序规则是每个元素的频率)。 下面使用数组‘heap’&…...
【图论】【分类讨论】LeetCode3017按距离统计房屋对数目
本文涉及的知识点 图论 分类讨论 本题同解 【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目 LeetCode3017按距离统计房屋对数目 给你三个 正整数 n 、x 和 y 。 在城市中,存在编号从 1 到 n 的房屋,由 n 条街道相连。对所有 …...
浅谈Yum 安装和 源码安装
浅谈Yum 安装和 源码安装 本文所叙述的Linux系统是基于RedHat发行版的CentOS7 yum安装 1. 前言 我们知道在Windows上下载的安装包后缀是 .exe ,与之对应的 在 Linux下的安装包的后缀是 .rpm rpm (Red Hat Package Manager) 是红帽软件包管理器 我们在Windows电脑…...
JavaEE初阶Day 3:多线程(1)
目录 Day 3:多线程(1)1. 线程1.1 引入线程的原因1.2 线程的定义1.3 为何线程更轻量1.4 问题 2. 多线程代码2.1 继承Thread重写run2.2 通过实现Runnable接口创建线程2.3 针对2.1的变形使用匿名内部类2.4 针对Runnable创建匿名内部类2.5 使用la…...
gutil140.dll是什么?gutil140.dll无法继续执行的解决方法
gutil140.dll文件是一个动态链接库(DLL)文件,通常与Microsoft Visual Studio 2015相关联。 gutil140.dll是开发过程中使用的工具函数集合,它辅助开发人员执行常见的编程任务,如文件操作、内存分配和字符串处理等。这个…...
在CentOS 7上安装Python 3.7.7
文章目录 一、实战步骤1. 安装编译工具2. 下载Python 3.7.7安装包3. 上传Python 3.7.7安装包4. 解压缩安装包5. 切换目录并编译安装6. 配置Python环境变量7. 使配置生效8. 验证安装是否成功 二、实战总结 一、实战步骤 1. 安装编译工具 在终端中执行以下命令 yum -y groupin…...
基于SpringBoot Vue宠物领养系统
一、📝功能介绍 基于SpringBoot Vue宠物领养系统 角色:管理员、用户 当游客打开系统的网址后,首先看到的就是首页界面。在这里,游客能够看到宠物领养救助平台的导航条显示首页、宠物招领、宠物认领、 宠物论坛、宠物资讯、后台管…...
ip命令
ip a 也是ip addr简写 [rootlocalhost ~]# ip a 1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00inet 127.0.0.1/8 scope host lovalid_lft forever preferred_lft…...
【Kaggle】练习赛《鲍鱼年龄预测》(上)
前言 上一篇文章,讲解了《肥胖风险的多类别预测》机器学习方面的文章,主要是多分类算法的运用,本文是一个回归的算法,本期是2024年4月份的题目《Regression with an Abalone Dataset》即《鲍鱼年龄预测》,在此分享高手…...
Ruby 之交租阶段信息生成
题目 我看了一下,这个题目应该不是什么机密,所以先放上来了。大概意思是根据合同信息生成交租阶段信息。 解答 要求是要使用 Ruby 生成交租阶段信息,由于时间比较仓促,变量名那些就用得随意了些。要点主要有下面这些:…...
RUST语言值所有权之内存复制与移动
1.RUST中每个值都有一个所有者,每次只能有一个所有者 String::from函数会为字符串hello分配一块内存 内存示例如下: 在内存分配前调用s1正常输出 在分配s1给s2后调用报错 因为s1分配给s2后,s1的指向自动失效 s1被move到s2 s1自动释放 字符串克隆使用...
【Django学习笔记(三)】BootStrap介绍
BootStrap介绍 前言正文1、BootStrap 快速了解2、初识BootStrap2.1 下载地址2.2 创建目录2.3 引入BootStrap2.4 使用BootStrap 3、BootStrap 组件&样式3.1 导航条3.2 栅格系统3.3 container3.3.1 container3.3.2 container-fluid 3.4 面板3.5 媒体对象3.6 分页3.7 图标3.7.…...
ClickHouse开发相关(UDAF)
ClickHouse开发相关(UDAF) ClickHouse介绍 ClickHouse是一个开源、高性能的列式 OLAP 数据库管理系统,用于使用 SQL 进行实时分析。 为什么需要ClickHouse UDAF? ClickHouse中已存在了许多聚合函数,绝大多数情况下已经覆盖我们的需求,但是有时候我们仍然需要自定义函数…...
MySql并发事务问题
事务 事务概念: 事务是一组操作的集合,它是一个不可分割的工作单位,事务会把所有的操作作为一个整体一起向系统提交或撤销操作请求,即这些操作要么同时成功,要么同时失败。 事务的特性:ACID: 小…...
Windows下Docker创建Mysql5.7
安装 下载镜像,注意,要带版本号 docker pull mysql:5.7 等下载完成执行命令: 错误命令1,直接Windows下路径: docker run --name mysql57 --restartalways -p 3306:3306 -v F:/mysqldata/data57/log:/var/log/mysql…...
Redis(性能管理、主从复制、哨兵模式)概述及部署
目录 一、性能管理 1、查看Redis内存使用 2、内存碎片率 3、跟踪内存碎片率 4、内存使用率 5、内回收key 二、Redis集群有三种模式 三、Redis主从复制 1、主从复制的概念 2、主从复制的作用 3、主从复制的流程 4、搭建Redis主从复制 1.环境准备 2.安装Redis&#…...
LabVIEW挖坑指南
一、挖坑指南 1.1、输出变量放在条件框内 错误写法: 现象:如果没进入对应的分支,输出为默认值 正常写法: 让每个分支输出的值都在预料之内。 1.2、统计耗时不准 错误写法 现象:统计出来的耗时是2000ms 正常写法&a…...
docker容器环境安装记录(MAC M1)(完善中)
0、背景 在MAC M1中搭建商城项目环境时,采用docker统一管理开发工具,期间碰到了许多环境安装问题,做个总结。 1、安装redis 在宿主机新建redis.conf文件运行创建容器命令,进行容器创建、端口映射、文件挂载、以指定配置文件启动…...
Linux 常用命令(持续更新中...)
1. ls 查看文件列表命令 语法: ls [-a -l -h] [Linux路径] -a -l -h 是可选的选项 (-h需配合-l命令一起使用)Linux路径是此命令可选的参数 ls #查看当前目录所有非隐藏文件(平铺方式显示) ls -a #查看当前目录下所有文件 …...
xss.pwnfunction-Jefff
在eval中可以直接执行命令所以直接把"直接闭合在结尾再加上一个"因为后面的"没闭和会报错 ?jeffa";alert(1);" 或 ?jeffa"-alert(1)-" -是分隔符...
java——文件上传
一、文件上传——简介 文件上传的简介:文件上传是指将本地计算机中的文件传输到网络上的服务器或另一台计算机上的过程。在 Web 开发中,文件上传通常指的是将用户通过 Web 页面提交的文件(如图像、文档、音频、视频等)传输到服务器…...
RCE(远程命令执行)漏洞详解
漏洞描述 RCE(remote command/code execute,远程命令执行)漏洞 远程代码执行 (RCE) 攻击是指攻击者可以在一个组织的计算机或网络上运行恶意代码。执行攻击者控制的代码的能力可用于各种目的,包括部署额外的恶意软件或窃取敏感数据。 漏洞原理 远程代…...
K8S - Deployment 的版本回滚
当前状态 先看deployment rootk8s-master:~# kubectl get deploy -o wide --show-labels NAME READY UP-TO-DATE AVAILABLE AGE CONTAINERS IMAGES …...
53 v-bind 和 v-model 的实现和区别
前言 这个主要的来源是 偶尔的情况下 出现的问题 就比如是 el-select 中选择组件之后, 视图不回显, 然后 model 不更新等等 这个 其实就是 vue 中 视图 -> 模型 的数据同步, 我们通常意义上的处理一般是通过 模型 -> 数据 的数据同步, 比如 我们代码里面更新了 model.…...
VMware-16.0配置虚拟机网络模式
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、为什么要配置网络?二、配置步骤1.检查VMware服务2.进入配置页面3.添加网络模式1.Bridge2.NAT3.Host-only 4.DHCP租约5.静态IP 三、使用总结 前言…...
element-ui badge 组件源码分享
今日简单分享 badge 组件的源码实现,主要从以下两个方面: 1、badge 组件页面结构 2、badge 组件属性 一、badge 组件页面结构 二、badge 组件属性 补充几个标签的用途: sub:下标、sup:上标、var 变量 代码如下&am…...
MySQL中日期有关函数
本次记录了获取日期时间的多种方式,还有日期和字符串之间的转换,以及加减日期的操作。 获取时间 # 1.获取当前时间(年月日时分秒格式) select now();# 2.获取当前时间(年月日格式) select curdate();# 3.获取当前时间(时分秒格式) select curtime();# 4.…...
jdbc工具类
jdbc 工具类,具体见下面代码,直接可以用。 /*** version 1.0* descpription: jdbc工具类* date 2024/4/6*/ public class JDBCUtils {private static final String URL "jdbc:mysql://127.0.0.1:3306/mybatis";private static final String …...
Svelte Web 框架介绍
Svelte 是一个用于构建网络应用程序的现代框架,它与其他用户界面框架(如React和Vue)有着本质的不同。Svelte 的核心理念是在构建应用程序时,将大部分工作转移到编译步骤中,而不是在用户的浏览器中运行时处理。这种方法…...
IP地址获取不到的原因是什么?
在数字化时代的今天,互联网已成为我们日常生活和工作中不可或缺的一部分。而IP地址,作为互联网通信的基础,其重要性不言而喻。然而,有时我们可能会遇到IP地址获取不到的问题,这会给我们的网络使用带来诸多不便。那么&a…...
矿业公司网站源码/中国域名注册局官网
请原谅我的天真,这是我第一次来这里,第一次处理java中的图形动画.我正在尝试完成一个沿着某种弧线移动的星形动画(试图在2d智能上模拟轨道).轨道动作与定时器一起用于为星星设置动画.简单地说,我已经在jpanel的不同位置画了几颗星.恒星y位置的平移取决于恒星远离x轴下降的距离,…...
基层组织建设部 网站/什么是互联网销售
html网页的主体标签是:body标签。body标签是一个网页的身体部分,用于定义网页的主体内容,是一个HTML文档中必须的部分。body元素中包含文档的所有内容(比如文本、超链接、图像、表格和列表等等)。HTML的主体标记是,在和中放置的是…...
企业营销型网站推广/百度广告联盟点击一次多少钱
试卷代号:0686 2017-2018年度第2学期期末考试 广告创意与表现(一)试题(闭卷) 2018年5月 一、填空题(每空1分,共10分) “创意”是一种_________________的过程和结果,这…...
阿拉善盟北京网站建设/seo推广小分享
摘要: 在这篇文章中,你将学会,如何利用百度地图API进行标注。如何使用API新增的打车费用接口。 ------------------------------------------------------------------------------------------------------- 哇,好久没有上来了。…...
server2012做网站/武汉百度网站优化公司
2022年终总结 回忆录 2022年焦虑和快乐是这一年中最大的两种情绪了。焦虑主要是因为心里的三块石头,从年初就开始悬着。第一块石头,科研论文录用,第二个石头,拿到国奖,第三个石头是拿到满意的offer。目前只剩下最后一…...
自己做直播网站/网站关键词排名优化工具
有两种防止重复提交: 禁用提交按钮发出请求令牌/ ID:禁用提交按钮 我们可以在函数调用HTTP请求之前禁用提交按钮,并在完成HTTP响应后再次启用它。该技术对于需要很长时间才能完成的过程(超过5秒)是有效的。由于不耐烦而无法获得结…...