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

ClickHouse:大数据领域的实时分析新宠

ClickHouse:大数据领域的实时分析新宠 关键词:ClickHouse、实时分析、列式存储、向量化执行、分布式数据库 摘要:在数据爆炸式增长的今天,企业对“实时看到数据价值”的需求越来越迫切。传统数据库在面对海量数据时,要么查询慢如蜗牛,要么成本高到离谱。而ClickHouse作为…...

新手福音:基于快马平台零基础入门Ubuntu与OpenClaw机器人开发

作为一个刚接触机器人开发的新手&#xff0c;最近在Ubuntu上折腾OpenClaw机器人开发时踩了不少坑。从环境配置到代码调试&#xff0c;每一步都让人头大。不过后来发现了InsCode(快马)平台&#xff0c;简直像找到了救星。今天就把我的学习过程整理成笔记&#xff0c;分享给同样想…...

开发提效新组合:用Cursor编写核心逻辑,快马平台一键生成完整企业级项目

今天想和大家分享一个提升开发效率的实用组合&#xff1a;用Cursor编写核心业务逻辑&#xff0c;再通过InsCode(快马)平台一键生成完整项目。最近在开发一个企业内部工时管理系统时&#xff0c;这套组合拳帮我节省了大量重复劳动时间。 1. 为什么选择这个技术组合 开发企业级…...

新手也能懂:DCDC芯片外围那个神秘的‘自举电容’,到底怎么选才不会翻车?

新手也能懂&#xff1a;DCDC芯片外围那个神秘的‘自举电容’&#xff0c;到底怎么选才不会翻车&#xff1f; 第一次看到DCDC芯片数据手册里的"自举电容"时&#xff0c;我盯着那个连接在BTST和SW引脚之间的小元件发呆了十分钟——它看起来和普通电容没什么两样&#x…...

算法审判日:用Git记录定程序员罪孽

一、版本控制的“审判台”在软件质量保障体系中&#xff0c;Git早已超越单纯的版本管理工具&#xff0c;演变为代码行为的“司法档案库”。每一次git commit都是程序员在数字法庭上的宣誓证词&#xff0c;而git blame则成为测试人员追溯缺陷根源的刑侦工具。罪证链条的三重维度…...

PrimeTime:默认配置文件

相关阅读 PrimeTimehttps://blog.csdn.net/weixin_45791458/category_12900271.html?spm1001.2014.3001.5482 当启动PrimeTime时&#xff0c;它会自动执行三个设置文件中的命令&#xff0c;这些文件具有相同的文件名.synopsys_pt.setup&#xff0c;但位于不同的目录中&#x…...

思考时爱用手托腮?警惕单侧发力拖垮颈肩平衡

很多人在工作、学习或思考时&#xff0c;习惯用手托腮&#xff0c;这个看似不经意的动作&#xff0c;会给颈肩带来持续负担&#xff0c;引发肌肉失衡劳损。用手托腮时&#xff0c;头部会向一侧倾斜&#xff0c;颈椎处于侧屈状态&#xff0c;颈部一侧肌肉持续紧张、牵拉&#xf…...

数据库优化:高效查询GUID的技巧

在日常的数据库操作中,如何高效地查询数据是一个永恒的话题。特别是当我们处理大型数据集和需要在文本字段中查找特定模式(如GUID)时,查询效率显得尤为关键。今天,我将分享一种优化查询GUID的方法,帮助你从长达数小时的查询时间中解脱出来。 背景 假设我们有一个数据库…...

打字侠全面支持三大五笔输入法:初学者快速上手指南

1. 五笔输入法&#xff1a;为什么值得初学者投入时间&#xff1f; 在拼音输入法大行其道的今天&#xff0c;很多初学者可能会疑惑&#xff1a;为什么要花时间学习看起来更复杂的五笔输入法&#xff1f;其实答案很简单——效率。我十年前刚开始接触五笔时也有同样的困惑&#xf…...

应用篇,在Silverlight中使用Virtual Earth地图服务

ilverlight应用中使用地图服务是否能够得心应手呢&#xff1f; 答案是肯定的&#xff0c;我们操作Earth服务只需执行简单的服务调用&#xff0c;就可完成坐地日行八万里的壮举了&#xff0c;而这一切是由VIEWs组件封装了Javascript脚本来完成的&#xff0c;通过对Virtual Eart…...