当前位置: 首页 > 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;特别是关于西门子的博图软件…...

5步精通Trilium中文版:构建高效个人知识管理系统

5步精通Trilium中文版&#xff1a;构建高效个人知识管理系统 【免费下载链接】trilium-translation Translation for Trilium Notes. Trilium Notes 中文适配, 体验优化 项目地址: https://gitcode.com/gh_mirrors/tr/trilium-translation 认识Trilium&#xff1a;重新定…...

Phi-4-mini-reasoning惊艳效果:自动识别题目所属数学分支并推荐解法策略

Phi-4-mini-reasoning惊艳效果&#xff1a;自动识别题目所属数学分支并推荐解法策略 1. 模型介绍 Phi-4-mini-reasoning是微软推出的3.8B参数轻量级开源模型&#xff0c;专为数学推理、逻辑推导和多步解题等强逻辑任务设计。这个模型主打"小参数、强推理、长上下文、低延…...

vLLM-v0.17.1GPU优化:显存碎片率<5%的PagedAttention内存管理实录

vLLM-v0.17.1 GPU优化&#xff1a;显存碎片率<5%的PagedAttention内存管理实录 1. vLLM框架简介 vLLM是一个专注于大语言模型(LLM)推理和服务的高性能开源库。这个项目最初由加州大学伯克利分校的天空计算实验室开发&#xff0c;现在已经发展成为一个由学术界和工业界共同…...

保姆级教程:在YOLOv8中手把手集成Coordinate Attention注意力模块(附完整配置文件)

零基础实战&#xff1a;在YOLOv8中集成Coordinate Attention注意力模块全流程解析 当你第一次看到Coordinate Attention&#xff08;坐标注意力&#xff09;这个名词时&#xff0c;可能会被它高大上的论文术语吓到。但别担心&#xff0c;今天我们就用最接地气的方式&#xff0…...

PowerBI进阶:除了DATEADD,这3种方法也能玩转同比环比(附场景选择指南)

PowerBI时间智能函数深度对比&#xff1a;突破DATEADD局限的实战指南 当你已经能熟练使用DATEADD计算同比环比&#xff0c;却发现报表加载速度越来越慢&#xff0c;或是遇到非标准财年分析需求时&#xff0c;是时候重新审视PowerBI的时间智能函数工具箱了。本文将带你深入剖析四…...

保姆级教程:用mintar版imu_utils搞定ZED2/Realsense相机内置IMU标定(避坑kalibr_allan)

保姆级教程&#xff1a;用mintar版imu_utils完成ZED2/Realsense相机IMU标定实战指南 当你在视觉惯性里程计&#xff08;VIO&#xff09;项目中遇到定位漂移问题时&#xff0c;很可能是因为IMU参数配置不当。与网上普遍推荐的kalibr_allan方法不同&#xff0c;本文将带你体验min…...

可视掏耳勺哪个牌子好?用什么掏耳朵最好?掏耳勺神器新款第一名

用什么掏耳朵最好&#xff1f;如今耳道护理成为家庭日常刚需&#xff0c;可视掏耳勺凭借“边看边清洁”的核心优势&#xff0c;彻底解决了传统盲掏易戳伤耳道、推深耳垢的痛点&#xff0c;成为越来越多人的首选。但当前可视掏耳勺市场陷入参数内卷&#xff0c;不少品牌盲目追求…...

动态透视报表 + 查询接口 + Excel导出

动态透视报表 查询接口 Excel导出 ✅ 动态行维度&#xff08;产品 / 型号 / 项目 任意组合&#xff09;✅ 动态列维度&#xff08;月份&#xff09;✅ a / f 子表头✅ SQL 透视&#xff08;适合 GaussDB&#xff09;✅ 查询接口 EasyExcel 导出接口✅ 可复用报表引擎 整体…...

OpenClaw 深度研究报告:从开源框架到企业级智能体平台的演进之路

一、核心定位&#xff1a;突破"对话天花板"的执行中枢 OpenClaw&#xff08;外号"龙虾"&#xff09; 是由奥地利工程师 Peter Steinberger 于 2025 年底开发的本地优先、模型无关的 AI 智能体运行框架。其核心价值主张极为鲜明&#xff1a; “The AI that …...

光伏产业发展带动紧固件需求增长 市场趋势与应用分析 上海紧固件专业展

2026第十六届上海紧固件专业展&#xff08;Fastener Expo Shanghai 2026&#xff09;将于6月24日至26日在上海国家会展中心举行。随着新能源产业持续升温&#xff0c;光伏行业的快速发展正在显著带动紧固件市场需求增长&#xff0c;成为行业关注的重要方向。在全球能源转型的大…...