采用非递归快排实现找出数组中的前k个高频元素(python)
前k个高频元素
- 题目描述
- 解题思路
- 代码实现
题目描述
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
解题思路
(1)先对给定的列表进行快速排序,按升序排(这里采用的非递归方式,因为最近在学习非递归快速排序的思想)
(2)非递归快速排序思想:找一个基准进行一趟快排,一般会产生两个区间,可以用一个栈保存这两个区间(区间类型[start,end]),并归位一个元素。
这是一次快速排序的结果,如果采用非递归,则需要对每一个入栈的区间一次次缩小范围,即循环判断栈 若不为空,则出栈,也就是拿出一个区间,继续下一趟快排,再归位一个元素,然后再判断产生的区间入栈,直到栈为空。
(3)快速排序结束后,原数组有序,这里找前k个高频元素,用字典存储每个元素的出现次数,并对字典进行降序排序,输出前k个key值。
代码实现
def frequentlyHighNo(nums, k):my_stack = []if len(nums)<=1:return numsmy_stack.append(0)my_stack.append(len(nums)-1)flag = 0while len(my_stack):j = my_stack.pop()i = my_stack.pop()begin = iend = jprint(begin, end)temp = nums[begin]print(temp)while begin < end:while begin < end and temp <= nums[end]:end -= 1while begin < end and temp >= nums[begin]:begin += 1if begin < end:nums[begin], nums[end] = nums[end], nums[begin]nums[i], nums[begin] = nums[begin], nums[i]mid = beginif i+1 < mid:my_stack.append(i)my_stack.append(mid-1)if mid < j-1:my_stack.append(mid+1)my_stack.append(j)res = {}for num in nums:if num not in res.keys():res[num] = 1else:res[num] += 1print(res)sorted_res = sorted(res.items(), key= lambda item: item[1], reverse=True)x_res = []u = 0while u<k:x_res.append(sorted_res[u][0])u+=1return x_res
相关文章:
采用非递归快排实现找出数组中的前k个高频元素(python)
前k个高频元素 题目描述解题思路代码实现 题目描述 给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 解题思路 (1)先对给定的列表进行…...
Java题集练习4
Java题集练习4 1 异常有什么用? 用来找到代码中产生的错误 防止运行出错2 异常在java中以什么形式存在? 异常在java中以类的形式存在,分为运行时异常和编译期异常,他们都在类Exception中3 异常是否可以自定义?如何自…...
sql进阶篇
1.更新记录 AC: update examination_info set tag replace(tag, "PYTHON", "Python") where tag "PYTHON";2.删除记录 AC: DELETE FROM exam_record WHERE timestampdiff(minute, start_time, submit_time) < 5AND…...
代码工艺:SQL 优化的细节
1. 巧用 limit 当出现深分页的时候,例如: select id, name, status, detail from product limit 100000, 30; 那么MySQL的执行方式为:一共需要查100030条数据,然后丢弃前面的100000条,只返回后面的30条数据…...
天池蚂蚁AFAC大模型挑战赛-冠军方案(含代码)
天池-蚂蚁AFAC大模型挑战赛-冠军方案 前言 ❝ 作者 彭欣怡 华东师大; 马千里 虾皮; 戎妍 港科广 说在前面 在当今信息技术迅猛发展的背景下,大模型技术已经成为推动人工智能领域进步的重要力量。 前段时间备受瞩目的AFAC赛题聚焦于金融对话…...
[QUIC] Packets 和 Frames 概述
Packets 和 Frames 概述 受保护的数据包 (Protected Packets) 基于不同的包类型, QUIC 使用不同等级的保护机制. Version Negotoation 包不受保护. Retry 包使用 AEAD 进行保护。 Initial 包使用 AEAD 进行保护, 但是使用的 Key 是由一个网络可见的值计算出来的。 因此 Ini…...
QT编辑框带行号
很可惜,qt的几个编辑框并没有相关功能。所以我们要自己实现一个。 先讲讲原理: QPlainTextEdit继承自QAbstractScrollArea,编辑发生在其viewport()的边距内。我们可以通过将视口的左边缘设置一个空白区域,…...
Kafka认证时Successfully logged in真的认证成功了?
背景 某个应用需要配置 Kafka 集群信息,且需要在验证集群是否可达。基本实现思路是创建一个生产者对象,然后发送一条测试数据,调用 Producer 的 send 方法发送消息后,再调用 get() 方法,即同步发送消息,测…...
软考信息系统管理师,系统集成项目管理工程师,考哪一个合适?
根据2024年的考试安排,高级项目管理师和系统集成工程师考试改为每年一次。 2024年上半年考高级项目管理师,下半年考系统集成项目管理工程师。 根据这个调整,建议先报名5月份的高级项目管理师考试。如果通过了,大家都高兴&#x…...
AI学习指南自然语言处理篇-位置编码(Positional Encoding)
AI学习指南自然语言处理篇-位置编码(Positional Encoding) 目录 引言位置编码的作用位置编码的原理绝对位置编码相对位置编码位置编码在Transformer中的应用位置编码的意义总结 引言 在自然语言处理中,文本数据通常以序列的形式存在。然而…...
macOS 15 Sequoia dmg格式转用于虚拟机的iso格式教程
想要把dmg格式转成iso格式,然后能在虚拟机上用,最起码新版的macOS镜像是不能用UltraISO,dmg2iso这种软件了,你直接转放到VMware里绝对读不出来,办法就是,在Mac系统中转换为cdr,然后再转成iso&am…...
【01初识】-初识 RabbitMQ
目录 学习背景1- 初识 MQ1-1 同步调用什么是同步调用?小结:同步调用优缺点 1-2 异步调用什么是异步调用?小结:异步调用的优缺点,什么时候使用异步调用? 1-3 MQ 技术选型 学习背景 异步通讯的特点ÿ…...
CTF-RE 从0到N:汇编层函数调用
windows 在 Windows 平台上的汇编语言中,调用函数的方式通常遵循特定的调用约定(Calling Convention)。最常见的调用约定包括: cdecl: C 默认调用约定,调用者清理堆栈。stdcall: Windows API 默认调用约定࿰…...
雷池社区版compose配置文件解析-mgt
在现代网络安全中,选择合适的 Web 应用防火墙至关重要。雷池(SafeLine)社区版免费切好用。为网站提供全面的保护,帮助网站抵御各种网络攻击。 compose.yml 文件是 Docker Compose 的核心文件,用于定义和管理多个 Dock…...
无人机避障——4D毫米波雷达Octomap从点云建立三维栅格地图
Octomap安装 sudo apt-get install ros-melodic-octomap-ros sudo apt-get install ros-melodic-octomap-msgs sudo apt-get install ros-melodic-octomap-server sudo apt-get install ros-melodic-octomap-rviz-plugins # map_server安装 sudo apt-get install ros-melodic-…...
Python(数据结构2)
常见数据结构 队列 队列(Queue),它是一种运算受限的线性表,先进先出(FIFO First In First Out) Python标准库中的queue模块提供了多种队列实现,包括普通队列、双端队列、优先队列等。 1 普通队列 queue.Queue 是 Python 标准库 queue 模块中的一个类…...
深入解析HTTP与HTTPS的区别及实现原理
文章目录 引言HTTP协议基础HTTP响应 HTTPS协议SSL/TLS协议 总结参考资料 引言 HTTP(HyperText Transfer Protocol)超文本传输协议是用于从Web服务器传输超文本到本地浏览器的主要协议。随着网络安全意识的提高,HTTPS(HTTP Secure…...
Java IO 模型
I/O 何为 I/O? I/O(Input/Output) 即输入/输出 。 我们先从计算机结构的角度来解读一下 I/O。 根据冯.诺依曼结构,计算机结构分为 5 大部分:运算器、控制器、存储器、输入设备、输出设备。 输入设备(比…...
安装双系统后ubuntu无法联网(没有wifi标识)网卡驱动为RTL8852BE
安装双系统后ubuntu没有办法联网,(本篇博客适用的版本为ubuntu20.04)且针对情况为无线网卡驱动未安装的情况 此时没有网络,可以使用手机数据线连接,使用USB共享网络便可解决无法下载的问题。 打开终端使用命令lshw -C …...
Sqoop的安装配置及使用
Sqoop安装前需要检查之前是否安装了Tez,否则会产生版本或依赖冲突,我们需要移除tez-site.xml,并将hadoop中的mapred-site.xml配置文件中的mapreduce驱动改回成yarn,然后分发到其他节点,hive里面配置的tez也要移除,然后…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
