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

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...