当前位置: 首页 > 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;然后…...

vLLM-v0.17.1行业落地:法律科技公司合同关键条款抽取与风险提示服务

vLLM-v0.17.1行业落地&#xff1a;法律科技公司合同关键条款抽取与风险提示服务 1. vLLM框架简介 vLLM是一个专为大型语言模型(LLM)设计的高性能推理和服务库&#xff0c;最初由加州大学伯克利分校的天空计算实验室开发&#xff0c;现已发展成为社区驱动的开源项目。这个框架…...

UniApp实战:如何安全高效地在安卓10+设备上实现本地数据存储(附权限配置避坑指南)

UniApp安卓10本地数据存储实战&#xff1a;权限配置与高性能方案设计 当你的UniApp在安卓10设备上突然无法保存用户配置时&#xff0c;控制台那行冰冷的"Permission denied"可能让整个开发团队陷入深夜加班。这不是简单的API调用问题&#xff0c;而是安卓存储机制变革…...

Linux驱动——uart子系统驱动注册分析

韦东山驱动大全uart子系统笔记自整理——08_UART驱动情景分析_注册由于韦东山老师uart子系统的08注册情景分析的笔记很简略&#xff0c;所以在学完这节课后自己整理了一份详细笔记&#xff0c;包含TTY驱动框架&#xff0c;数据结构分析&#xff0c;以及注册过程分析&#xff0c…...

Cadence Virtuoso IC618版图验证全流程:解决PEX提参map error的详细步骤

Cadence Virtuoso IC618版图验证全流程&#xff1a;解决PEX提参map error的详细步骤 从IC514迁移到IC618的过程就像给老房子换新地基——表面上看功能相似&#xff0c;但底层架构的升级带来了全新的操作逻辑和隐藏的"陷阱"。最近三个月&#xff0c;我团队完成了7个项…...

统计建模大赛的评分标准

2026年统计建模大赛正在进行中&#xff0c;相关文章&#xff1a; 统计建模大赛去哪找数据&#xff1f; 2026年统计建模大赛AI工具使用规范 2026年统计建模大赛选题思路——数字经济统计监测体系研究 我在公开课以及以前的文章中经常强调&#xff0c;数模竞赛不是考试&#…...

Qwen3-VL:30B多模态大模型在飞书智能办公中的实战应用

Qwen3-VL:30B多模态大模型在飞书智能办公中的实战应用 飞书作为现代企业智能办公平台&#xff0c;如何通过多模态大模型实现真正的智能化升级&#xff1f;本文将带你从零搭建企业级AI助手&#xff0c;让图文交互能力真正落地业务场景。 1. 为什么企业需要多模态AI助手&#xff…...

泛微OA Ecology 安全补丁管理账号配置与实战

1. 泛微OA Ecology安全补丁管理账号配置详解 第一次接触泛微OA Ecology系统的安全补丁管理功能时&#xff0c;我完全没意识到这个看似简单的配置背后藏着这么多门道。直到有次系统被恶意攻击&#xff0c;才发现默认的管理账号存在安全隐患。今天就带大家彻底搞懂这个关键配置&a…...

魔兽世界API开发助手:从新手到专家的全流程解决方案

魔兽世界API开发助手&#xff1a;从新手到专家的全流程解决方案 【免费下载链接】wow_api Documents of wow API -- 魔兽世界API资料以及宏工具 项目地址: https://gitcode.com/gh_mirrors/wo/wow_api 价值定位&#xff1a;如何避免90%的插件开发陷阱&#xff1f; 在魔…...

ESP8266-ESP32 物联网开发入门

ESP8266/ESP32物联网开发入门指南 在智能家居、远程监控和工业自动化等领域&#xff0c;物联网技术正快速改变我们的生活。作为物联网开发的热门选择&#xff0c;ESP8266和ESP32凭借低成本、高性能和丰富的开发资源&#xff0c;成为初学者和工程师的首选。本文将介绍如何快速入…...

5步快速解锁付费内容:bypass-paywalls-chrome-clean终极指南 [特殊字符]

5步快速解锁付费内容&#xff1a;bypass-paywalls-chrome-clean终极指南 &#x1f680; 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 在信息爆炸的时代&#xff0c;你是否经常遇到优…...