【深基9.例4】求第 k 小的数#洛谷(MLE)

题目描述

输入 n n n 1 ≤ n < 5000000 1 \le n < 5000000 1n<5000000 n n n 为奇数)个数字 a i a_i ai 1 ≤ a i < 10 9 1 \le a_i < {10}^9 1ai<109),输出这些数字的第 k k k 小的数。最小的数是第 0 0 0 小。

请尽量不要使用 nth_element 来写本题,因为本题的重点在于练习分治算法。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2
n,m=map(int,input().split())
mapp=list(map(int,input().split()))
mapp.sort()
print(mapp[m])

请添加图片描述
这样子写,超内存认了。但是我用分治思想,也就是快排的变形,写出来还是超内存

def qsort(begin,end):global mapp,mleft = beginright = endvalue_mid=mapp[int((left+right)/2)]while left<=right:while mapp[right] > value_mid:right -= 1while mapp[left] < value_mid:left += 1if left <= right:flag = mapp[left]mapp[left] = mapp[right]mapp[right] = flagleft += 1right -= 1if m<=right:qsort(begin,right)elif left<=m:qsort(left,end)else:print(mapp[right+1])return 0if __name__=="__main__":n, m = map(int, input().split())mapp = list(map(int, input().split()))qsort(0, n - 1)

请添加图片描述
和快排的思想一样,每一步都把对照参照值,数大的放在右边,数小的放在左边。然后和m进行比较,如果比m大就递归左边的部分,如果小就递归右边的部分。最后数列分成三部分。分别是左边小的,中间一样的,以及右边大的。最后可以得到第m小的数。但是还是超了。不理解了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/238407.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

友思特分享丨高精度彩色3D相机:开启崭新的彩色3D成像时代

来源&#xff1a;友思特 机器视觉与光电 友思特分享丨高精度彩色3D相机&#xff1a;开启崭新的彩色3D成像时代 原文链接&#xff1a;https://mp.weixin.qq.com/s/vPkfA5NizmiZmLiy_jv3Jg 欢迎关注虹科&#xff0c;为您提供最新资讯&#xff01; 3D成像的新时代 近年来&#…

pycharm Terminal命令行设置默认是Windows Powershell运行报错怎么修改?

目录 1. 真实案例 2. 如何做 3. 流程 3.1. 打开 settings 3.2. 在 最上方搜索 terminal 3.3. 在 shell path 里选择 cmd&#xff0c;并点击 OK 3.4. 重新打开 terminal 就成功了 1. 真实案例 使用 Windows Powershell 运行部分命令会不显示 2. 如何做 需要修改底部默认…

Android Studio安卓读写NFC Ntag标签源码

本示例使用的发卡器&#xff1a; https://item.taobao.com/item.htm?spma1z10.5-c-s.w4002-21818769070.11.3513789erHXVGx&id615391857885 <?xml version"1.0" encoding"utf-8"?> <androidx.constraintlayout.widget.ConstraintLayout x…

“语言服务40人论坛2023年年会”在北京举行

为充分发挥区域合作优势&#xff0c;深度推进翻译专业学位研究生培养模式和路径建设&#xff0c;提升翻译人才培养质量&#xff0c;推动京津冀地区教育协同发展&#xff0c;为中国高质量发展提供语言服务智慧和方案&#xff0c;1月13日至14日&#xff0c;“语言服务40人论坛202…

嵌入式学习-网络编程-Day1

Day1 思维导图 作业 实现一下套接字通信 代码 #include<myhead.h>int main(int argc, const char *argv[]) {//1、创建套接字int sfd socket(AF_INET, SOCK_STREAM, 0);//参数1&#xff1a;通信域&#xff1a;使用的是ipv4通信//参数2&#xff1a;表示使用tcp通信//参…

继承、修饰符、工具类、jar包

目录 1.继承 2.修饰符 3.工具类 4.jar包的制作与使用 1.继承 是什么 1.面向对象的三大特征之一&#xff08;封装、继承、多态&#xff09; 2.可以使得子类具有父类的属性和方法&#xff0c;还可以在子类中重新定义&#xff0c;追加属性和方法。 继承的格式 public class F…

并发编程(一)线程基础知识与线程控制

进程与线程 进程&#xff1a;如任务管理器中各种程序叫做正在运行的进程。对于操作系统来说&#xff0c;仅仅是一个数据结构&#xff0c;并不真实的执行代码 线程&#xff1a;真实执行代码的 每个进程启动的是时候会同步启动一个主线程即main函数&#xff0c;当main函数结束…

智慧公厕:引领城市卫生管理新时代

在智慧城市建设中&#xff0c;智慧公厕作为城市环境卫生信息化的重要组成部分&#xff0c;扮演着关键角色。它不仅可以提升城市管理水平&#xff0c;满足人民群众的需求&#xff0c;还能提高公厕使用体验和城市环境卫生水平。如广州中期科技有限公司自主研发的智慧公厕管理系统…

第10章 通信业务

文章目录 10.1.1 通信行业1、通信行业的界定2、通信行业的特点 10.1.2 通信企业10.1.3 通信终端1、通信终端的分类2、终端发展趋势 10.2.1 通信业务的定义及分类10.2.2 基础电信业务1、第一类基础电信业务A11 固定通信业务A12 蜂窝移动通信业务A13 第一类卫星通信业务A14 第一类…

代码随想录 Leetcode1. 两数之和

题目&#xff1a; 代码&#xff08;首刷看解析 2024年1月15日&#xff09;&#xff1a; class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {int another 0;unordered_map<int,int> hash;for(int i 0; i < nums.size();…

为什么有人说PMP是水证,它的含金量到底怎么样?

在我国大陆&#xff0c;有好多证书被商业化得太重了&#xff0c;甚至演变成了个人或一些公司摇钱的工具。所以有些证书受人吹捧它崛起的快&#xff0c;但是活不长&#xff0c;甚至“夭折”&#xff0c;比如以前微软系列的证书&#xff1b; 而PMP认证从国外引进大陆这么多年了&…

NLP(十八):LLM 的推理优化技术纵览

原文&#xff1a;NLP&#xff08;十八&#xff09;&#xff1a;LLM 的推理优化技术纵览 - 知乎 目录 收起 一、子图融合&#xff08;subgraph fusion&#xff09; 1.1 FasterTransformer by NVIDIA 1.2 DeepSpeed Inference by Microsoft 1.3 MLC LLM by TVM 二、模型压…

Grind75第10天 | 133.克隆图、994.腐烂的橘子、79.单词搜索

133.克隆图 题目链接&#xff1a;https://leetcode.com/problems/clone-graph 解法&#xff1a; 这个题是对无向图的遍历&#xff0c;可以用深度优先搜索和广度有限搜索。 下面这个图比较清楚的说明了两种方法的区别。 DFS&#xff1a;从A开始克隆&#xff0c;遍历两个邻居…

数据结构期末复习(C语言版)

一、绪论 1.数据结构的术语 数据&#xff1a;所有能输入计算机并被计算机程序处理的符号的总称&#xff1b;数据元素&#xff1a;数据的基本单位&#xff1b;数据项&#xff1a;组成数据元素的、有独立含义的、不可分割的最小单位&#xff1b;数据对象&#xff1a;是性质相同…

springboot基于WEB的旅游推荐系统设计与实现

&#x1f345;点赞收藏关注 → 私信领取本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345;一 、设计说明 1.1选题动因 当前…

云原生微服务之分布式锁框架 Redisson

&#x1f339;作者主页&#xff1a;青花锁 &#x1f339;简介&#xff1a;Java领域优质创作者&#x1f3c6;、Java微服务架构公号作者&#x1f604; &#x1f339;简历模板、学习资料、面试题库、技术互助 &#x1f339;文末获取联系方式 &#x1f4dd; 系列专栏目录 [Java项目…

阿里云国际服务器设置安全防护程序

阿里云云服务器&#xff08;ECS&#xff09;提供弹性、安全、高性能、高性价比的虚拟云服务器&#xff0c;满足您的所有需求。立即在这里免费注册&#xff01; 常见 Web 应用程序 请勿对 Web 服务控制台&#xff08;如 WDCP、TOMCAT、Apache、Nginx、Jekins、PHPMyAdmin、Web…

陪诊小程序开发|陪诊软件定制|陪诊系统成品功能包含哪些?

陪诊小程序是一种便捷的工具&#xff0c;为用户提供一系列服务和功能&#xff0c;方便患者在就医过程中获得更好的体验和效果。接下来我们将介绍几个主要的陪诊小程序功能。 陪诊小程序开发功能&#xff1a; 一、预约挂号功能。陪诊小程序能够连接用户和医疗机构的系统&#x…

从头安装与使用一个docker GPU环境

GPU版docker的安装与使用 欢迎使用GPU版docker安装使用说明使用官方教程安装docker新建一个GPU版docker环境调用docker环境执行本地python文件 欢迎使用GPU版docker安装使用说明 使用官方教程安装docker 导入源仓库的GPG key curl -fsSL https://download.docker.com/linux/…

虹科分享 | 用Redis为LangChain定制AI代理——OpenGPTs

文章速览&#xff1a; OpenGPTs简介Redis在OpenGPTs中的作用在本地使用OpenGPTs在云端使用OpenGPTsRedis与LangChain赋能创新 OpenAI最近推出了OpenAI GPTs——一个构建定制化AI代理的无代码“应用商店”&#xff0c;随后LangChain开发了类似的开源工具OpenGPTs。OpenGPTs是一…