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

洛谷_P1923 【深基9.例4】求第 k 小的数_python写法

 哪位大佬可以出一下这个的题解?????话说蓝桥杯可以用numpy库吗??????

这道题有一个很简单的思路就是排序完成之后再访问。

but有很大的问题,压根就不能通过,那怎么办呢?

百度一下找到答案,看到网上分享说这道题应该用分治+快速排序的算法,那我们首先来学习一下这两个是个什么事儿。

快速排序【分治思想 + python实现 含图解】_python分治算法排序-CSDN博客

1.分治是一种思想

        分治就是将一个大问题分成若干个小问题去处理,当每一个小问题都得到了解决那么一整个问题也算是得到了解决,

2.快速排序

        那我这部分的笔记就是参考上面那篇博客来的,感觉这篇笔记很适合我们小白学习。

这篇笔记的图解就非常详细。

        看完图解之后差不多就可以理解快速排序到底是快在哪里。

        那快速排序的代码怎么完成呢?我们如何完成上图的一系列操作呢。其实快速排序最重要的一个点在于列表中每一个元素都有一个应有的位置,怎么找到这个正确的位置就是我们需要解决的。现在我们捋一下思路。

快速排序思路(升序为例):

        根绝上面的图解我们知道,所谓每一个元素自己正确的位置意思是这个元素左边的元素都会小于他,右边的元素都会大于他,当每一个元素都满足这样的要求那么说明整个列表排序完成。

def quick_sort(nums, start, end):if start >= end:returnpivot, l, r = nums[start], start, endwhile l < r:while nums[r] >= pivot and l < r:r -= 1while nums[l] <= pivot and l < r:l += 1nums[l], nums[r] = nums[r], nums[l]nums[start], nums[r] = nums[r], nums[start]

5.分治模块
1)此时,下标为 r 的元素(就是之前选的 pivot)已经排在了正确的位置,左边都 <= pivot,右边都 >= pivot,那么我们再对左半部分 nums 和右半部分 nums 分别进行排序即可。
2)左边的起始下标仍为 start,终止下标变成了 r-1,因为 nums[r] 已经排好序不用再加上了;右边同理,起始为 r+1,终止为 end。
3)如果最后一轮排序找到的 r 就等于列表起始下标start,或者 r 就等于列表终止下标end,那么显然start > r-1 或者 r+1>end,则下一次的quick_sort 中有 start>end,所以终止条件中会有出现 start>end 时直接返回的这种情况。

3.代码

def quick_sort(nums, start, end):if start >= end:returnpivot, l, r = nums[start], start, endwhile l < r:while nums[r] >= pivot and l < r:r -= 1while nums[l] <= pivot and l < r:l += 1nums[l], nums[r] = nums[r], nums[l]nums[start], nums[r] = nums[r], nums[start]quick_sort(nums, start, r - 1)quick_sort(nums, r + 1, end)def f(nums):quick_sort(nums, 0, len(nums) - 1)return numsnums1 = [3, 2, 3, 1, 2, 4, 5, 5, 6]
print(f(nums1))

4.题解

错了但是我不知道错在哪里了

n, k = map(int, input().split(' '))
x = list(map(int, input().split(' ')))def qsort(l, r):i, j, mid = l, r, x[(l + r) // 2]while i <= j:while x[j] > mid:j -= 1while x[i] < mid:i += 1if i <= j:x[i], x[j] = x[j], x[i]i += 1j -= 1# 快排后数组被划分为三块: l<=j<=i<=rif k <= j:qsort(l, j)elif i <= k:# 在右区间只需要搜右区间qsort(i, r)else:# 如果在中间区间直接输出print(x[k])qsort(0, n - 1)

哪位大佬可以出一下这个的题解?????话说蓝桥杯可以用numpy库吗??????

相关文章:

洛谷_P1923 【深基9.例4】求第 k 小的数_python写法

哪位大佬可以出一下这个的题解&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;话说蓝桥杯可以用numpy库吗&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f; 这道题有一个很简单的思路就是排序完成之后再访问。 but有很大的问题&…...

【MySQL】学习约束和使用图形化界面创建表

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-iqtbME2KmWpQFQSt {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…...

QGIS编译(跨平台编译)之四十八:pixman编译(Windows、Linux、MacOS环境下编译)

文章目录 一、pixman介绍二、pixman下载三、Linux下编译四、MacOS下编译五、Windows下编译一、pixman介绍 Pixman 是一个开源的图形库,它提供了底层像素操作功能,包括像素格式转换、图像合成、图像缩放、图像旋转等多种操作。Pixman 主要被用作 Cairo 图形库的后端,支持 Ca…...

华为数通方向HCIP-DataCom H12-821题库(单选题:441-460)

第441题 下面是一台路由输出的信息,关于这段信息描述正确的是 <R1>display bgp peerBGP local router ID : 2.2.2.2Local AS number : 100Total number of peers : 2 Peers in established state : 0Peer V AS MsgRcvd MsgSent OutQ Up/Down …...

【sass】 中使用 /deep/ 修改 elementUI 组件样式报错

element plus 想要覆盖组件的样式&#xff0c;想到了/deep/样式穿透&#xff0c;但样式一直不生效&#xff0c;代码如下&#xff1a; <style scoped lang"sass"> .main_wrapper{padding: 0 53pxposition: relativetop: -20px } >>> .el-tabs__item{h…...

Python算法题集_排序链表

Python算法题集_排序链表 题148&#xff1a;排序链表1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【冒泡大法】2) 改进版一【列表排序】3) 改进版二【数值归并排序】4) 改进版三【快慢指针归并排序】 4. 最优算法 本文为Python算法题集之一的…...

红日靶场2学习

靶场下载来自&#xff1a; http://vulnstack.qiyuanxuetang.net/vuln/detail/3/ 靶场统一登录密码&#xff1a;1qazWSX 按大佬的说法是 环境需要模拟内网和外网两个网段&#xff0c;PC端虚拟机相当于网关服务器&#xff0c;所以需要两张网卡&#xff0c;一个用来向外网提供web…...

将 下载下来的 jar 包 安装到本地的 maven 仓库中

使用管理员权限 打开一个 cmd 窗口输入 mvn -v 查看 maven 版本由于之前 并没有这样的操作所以第一次 执行的时候 提示 命令不存在所以需要将 maven 软件中的 bin 文件的目录 添加到 环境变量中 的 path 变量 中本机路径为:D:\Program Files (x86)\apache-maven-3.5.2\bin C:\…...

Qt初使用(使用Qt创建项目,在创建的项目中添加类,Qt中输出内容到控制台,设置窗口大小和窗口标题,Qt查看说明文档)

目录 一.创建带模板的项目新建项目运行在文件中查看该项目文件 二.在创建好的项目中添加类三.创建空项目&#xff08;不使用自带的模板&#xff09;四.Qt中输出内容到控制台五.设置窗口大小 , 窗口标题 ,固定窗口大小QWidget组件的说明 六.Pro文件帮助文档 按windows键&#xf…...

【黑马程序员】C++运算符重载

文章目录 运算符重载加号运算符重载成员函数实现运算符重载全局函数实现运算符重载全局函数实现函数重载 左移运算符重载递增运算符重载赋值运算符重载关系运算符重载函数调用运算符重载 运算符重载 对已有的运算符重新进行定义&#xff0c;赋予其另一种功能&#xff0c;以适应…...

Java中的乐观锁和悲观锁

使用场景及用法 悲观锁 总是假设最坏的情况&#xff0c;每次去拿数据的时候都认为别人会修改&#xff0c;所以每次在拿数据的时候都会上锁&#xff0c;这样别人想拿这个数据就会阻塞直到它拿到锁&#xff08;共享资源每次只给一个线程使用&#xff0c;其它线程阻塞&#xff0c;…...

从Unity到Three.js(计时器、Transform)

计时器、模型对象平移函数、枚举定义的使用 对应unity中的一些常用功能 import * as THREE from three;const scene new THREE.Scene(); const camera new THREE.PerspectiveCamera(60, window.innerWidth / window.innerHeight, 0.1, 1000);const renderer new THREE.WebG…...

红日靶场(初学)

按照以前的来说一般是有两层网络的内网和外网 这个也是这样的 所以需要两张网卡&#xff0c;一个用来向外网提供web服务&#xff0c;一个是通向内网 以下就是配置 以下就是一些相关信息 外网网段是写成了192.168.111.1/24 WEB PC DC kali 开始扫描 nmap -sS -sV -Pn -T4 19…...

【PyTorch】改变张量(Tensor)形状操作

PyTorch深度学习总结 第二章 PyTorch中改变张量(Tensor)形状操作 文章目录 PyTorch深度学习总结一、前言二、改变张量形状 一、前言 上文讲解了张量生成和信息获取的知识&#xff0c;本文将针对张量的操作进行详细讲解。 二、改变张量形状 1、改变张量形状的函数总结&#x…...

《金融人工智能:用python实现ai量化交易》

融合了数学、python、深度学习以及金融知识&#xff0c;是本推荐的好书。请收藏本文&#xff0c;读后再给大学总结。...

位运算+leetcode ( 2 )

题一&#xff1a;只出现一次的数字&#xff08;1&#xff09; 1.链接 136. 只出现一次的数字 - 力扣&#xff08;LeetCode&#xff09; 2.思想 借用位运算中异或操作符的特点&#xff0c;a^a0&#xff0c;0^aa先定义一个sum0就用一个循环来遍历这个数组&#xff0c;每次都进行…...

17 ABCD数码管显示与动态扫描原理

1. 驱动八位数码管循环点亮 1.1 数码管结构图 数码管有两种结构&#xff0c;共阴极和共阳极&#xff0c;ACX720板上的是共阳极数码管&#xff0c;低电平点亮。 1.2 三位数码管等效电路图 为了节约I/O接口&#xff0c;各个数码管的各段发光管被连在一起&#xff0c;通过sel端…...

【Zigbee课程设计系列文章】Zigbee开发环境搭建

【Zigbee课程设计系列文章】Zigbee开发环境搭建 前言IAR 下载安装Z-Stack协议栈安装 &#x1f38a;项目专栏&#xff1a;【Zigbee课程设计系列文章】&#xff08;附详细使用教程完整代码原理图完整课设报告&#xff09; 前言 &#x1f451;由于无线传感器网络&#xff08;也即…...

[Linux开发工具]项目自动化构建工具-make/Makefile

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 目录 1.背景2.依赖关系和依…...

PLC_博图系列☞参数实例

PLC_博图系列☞参数实例 文章目录 PLC_博图系列☞参数实例背景介绍参数实例参数实例的工作原理创建参数实例将实例作为参数传送 关键字&#xff1a; PLC、 西门子、 博图、 Siemens 、 参数实例 背景介绍 这是一篇关于PLC编程的文章&#xff0c;特别是关于西门子的博图软件…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...