当前位置: 首页 > news >正文

采用非递归快排实现找出数组中的前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 &#xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 解题思路 &#xff08;1&#xff09;先对给定的列表进行…...

Java题集练习4

Java题集练习4 1 异常有什么用&#xff1f; 用来找到代码中产生的错误 防止运行出错2 异常在java中以什么形式存在&#xff1f; 异常在java中以类的形式存在&#xff0c;分为运行时异常和编译期异常&#xff0c;他们都在类Exception中3 异常是否可以自定义&#xff1f;如何自…...

sql进阶篇

1.更新记录 AC&#xff1a; update examination_info set tag replace(tag, "PYTHON", "Python") where tag "PYTHON";2.删除记录 AC&#xff1a; DELETE FROM exam_record WHERE timestampdiff(minute, start_time, submit_time) < 5AND…...

代码工艺:SQL 优化的细节

1. 巧用 limit 当出现深分页的时候&#xff0c;例如&#xff1a; select id, name, status, detail from product limit 100000, 30; 那么MySQL的执行方式为&#xff1a;一共需要查100030条数据&#xff0c;然后丢弃前面的100000条&#xff0c;只返回后面的30条数据&#xf…...

天池蚂蚁AFAC大模型挑战赛-冠军方案(含代码)

天池-蚂蚁AFAC大模型挑战赛-冠军方案 前言 ❝ 作者     彭欣怡 华东师大; 马千里 虾皮; 戎妍 港科广 说在前面     在当今信息技术迅猛发展的背景下&#xff0c;大模型技术已经成为推动人工智能领域进步的重要力量。     前段时间备受瞩目的AFAC赛题聚焦于金融对话…...

[QUIC] Packets 和 Frames 概述

Packets 和 Frames 概述 受保护的数据包 (Protected Packets) 基于不同的包类型, QUIC 使用不同等级的保护机制. Version Negotoation 包不受保护. Retry 包使用 AEAD 进行保护。 Initial 包使用 AEAD 进行保护, 但是使用的 Key 是由一个网络可见的值计算出来的。 因此 Ini…...

QT编辑框带行号

很可惜&#xff0c;qt的几个编辑框并没有相关功能。所以我们要自己实现一个。 先讲讲原理&#xff1a; QPlainTextEdit继承自QAbstractScrollArea&#xff0c;编辑发生在其viewport&#xff08;&#xff09;的边距内。我们可以通过将视口的左边缘设置一个空白区域&#xff0c;…...

Kafka认证时Successfully logged in真的认证成功了?

背景 某个应用需要配置 Kafka 集群信息&#xff0c;且需要在验证集群是否可达。基本实现思路是创建一个生产者对象&#xff0c;然后发送一条测试数据&#xff0c;调用 Producer 的 send 方法发送消息后&#xff0c;再调用 get() 方法&#xff0c;即同步发送消息&#xff0c;测…...

软考信息系统管理师,系统集成项目管理工程师,考哪一个合适?

根据2024年的考试安排&#xff0c;高级项目管理师和系统集成工程师考试改为每年一次。 2024年上半年考高级项目管理师&#xff0c;下半年考系统集成项目管理工程师。 根据这个调整&#xff0c;建议先报名5月份的高级项目管理师考试。如果通过了&#xff0c;大家都高兴&#x…...

AI学习指南自然语言处理篇-位置编码(Positional Encoding)

AI学习指南自然语言处理篇-位置编码&#xff08;Positional Encoding&#xff09; 目录 引言位置编码的作用位置编码的原理绝对位置编码相对位置编码位置编码在Transformer中的应用位置编码的意义总结 引言 在自然语言处理中&#xff0c;文本数据通常以序列的形式存在。然而…...

macOS 15 Sequoia dmg格式转用于虚拟机的iso格式教程

想要把dmg格式转成iso格式&#xff0c;然后能在虚拟机上用&#xff0c;最起码新版的macOS镜像是不能用UltraISO&#xff0c;dmg2iso这种软件了&#xff0c;你直接转放到VMware里绝对读不出来&#xff0c;办法就是&#xff0c;在Mac系统中转换为cdr&#xff0c;然后再转成iso&am…...

【01初识】-初识 RabbitMQ

目录 学习背景1- 初识 MQ1-1 同步调用什么是同步调用&#xff1f;小结&#xff1a;同步调用优缺点 1-2 异步调用什么是异步调用&#xff1f;小结&#xff1a;异步调用的优缺点&#xff0c;什么时候使用异步调用&#xff1f; 1-3 MQ 技术选型 学习背景 异步通讯的特点&#xff…...

CTF-RE 从0到N:汇编层函数调用

windows 在 Windows 平台上的汇编语言中&#xff0c;调用函数的方式通常遵循特定的调用约定&#xff08;Calling Convention&#xff09;。最常见的调用约定包括&#xff1a; cdecl: C 默认调用约定&#xff0c;调用者清理堆栈。stdcall: Windows API 默认调用约定&#xff0…...

雷池社区版compose配置文件解析-mgt

在现代网络安全中&#xff0c;选择合适的 Web 应用防火墙至关重要。雷池&#xff08;SafeLine&#xff09;社区版免费切好用。为网站提供全面的保护&#xff0c;帮助网站抵御各种网络攻击。 compose.yml 文件是 Docker Compose 的核心文件&#xff0c;用于定义和管理多个 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)&#xff0c;它是一种运算受限的线性表,先进先出(FIFO First In First Out) Python标准库中的queue模块提供了多种队列实现&#xff0c;包括普通队列、双端队列、优先队列等。 1 普通队列 queue.Queue 是 Python 标准库 queue 模块中的一个类…...

深入解析HTTP与HTTPS的区别及实现原理

文章目录 引言HTTP协议基础HTTP响应 HTTPS协议SSL/TLS协议 总结参考资料 引言 HTTP&#xff08;HyperText Transfer Protocol&#xff09;超文本传输协议是用于从Web服务器传输超文本到本地浏览器的主要协议。随着网络安全意识的提高&#xff0c;HTTPS&#xff08;HTTP Secure…...

Java IO 模型

I/O 何为 I/O? I/O&#xff08;Input/Output&#xff09; 即输入&#xff0f;输出 。 我们先从计算机结构的角度来解读一下 I/O。 根据冯.诺依曼结构&#xff0c;计算机结构分为 5 大部分&#xff1a;运算器、控制器、存储器、输入设备、输出设备。 输入设备&#xff08;比…...

安装双系统后ubuntu无法联网(没有wifi标识)网卡驱动为RTL8852BE

安装双系统后ubuntu没有办法联网&#xff0c;&#xff08;本篇博客适用的版本为ubuntu20.04&#xff09;且针对情况为无线网卡驱动未安装的情况 此时没有网络&#xff0c;可以使用手机数据线连接&#xff0c;使用USB共享网络便可解决无法下载的问题。 打开终端使用命令lshw -C …...

Sqoop的安装配置及使用

Sqoop安装前需要检查之前是否安装了Tez,否则会产生版本或依赖冲突&#xff0c;我们需要移除tez-site.xml&#xff0c;并将hadoop中的mapred-site.xml配置文件中的mapreduce驱动改回成yarn&#xff0c;然后分发到其他节点&#xff0c;hive里面配置的tez也要移除&#xff0c;然后…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...