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

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

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

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

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

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

1.分治是一种思想

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

2.快速排序

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

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

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

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

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

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

def quick_sort(nums, start, end):
    if start >= end:
        return

    pivot, l, r = nums[start], start, end

    while l < r:
        while nums[r] >= pivot and l < r:
            r -= 1
        while nums[l] <= pivot and l < r:
            l += 1
        nums[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:
        return

    pivot, l, r = nums[start], start, end

    while l < r:
        while nums[r] >= pivot and l < r:
            r -= 1
        while nums[l] <= pivot and l < r:
            l += 1
        nums[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 nums


nums1 = [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 -= 1
        while x[i] < mid:
            i += 1
        if i <= j:
            x[i], x[j] = x[j], x[i]
            i += 1
            j -= 1
    # 快排后数组被划分为三块: l<=j<=i<=r
    if k <= j:
        qsort(l, j)
    elif i <= k:
        # 在右区间只需要搜右区间
        qsort(i, r)
    else:
        # 如果在中间区间直接输出
        print(x[k])

qsort(0, n - 1)

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

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

安装Windows XP系统

1.镜像安装 镜像安装:Windows XP 2.安装过程(直接以图的形式呈现) 按ENTER继续,F8继续 ENTER继续安装 WIN xp 秘钥 CKWMY-66QR4-V96B7-DTYP3-YMM8B 等待安装即可

「优选算法刷题」:和可被K整除的子数组

一、题目 给定一个整数数组 nums 和一个整数 k &#xff0c;返回其中元素之和可被 k 整除的&#xff08;连续、非空&#xff09; 子数组 的数目。 子数组 是数组的 连续 部分。 示例 1&#xff1a; 输入&#xff1a;nums [4,5,0,-2,-3,1], k 5 输出&#xff1a;7 解释&…

代码随想录算法训练营第32天 | 122.买卖股票的最佳时机II , 55. 跳跃游戏 , 45.跳跃游戏II

贪心算法章节理论基础&#xff1a; https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 122.买卖股票的最佳时机II 题目链接&#xff1a;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ 思路…

解决Windows更新后无法启动的十种办法,总有一种适合你

你可能已经更新了操作系统以修复错误或使用最新功能。但是,如果Windows在更新后无法启动呢? 如果你面临这样的问题,主要是由于安装文件中的错误或你的系统与最新更新不兼容。此外,损坏的MBR或驱动程序也会阻止电脑启动。 不管是什么原因,本文将用十种简单的技术来指导你…

耳机壳UV树脂制作私模定制耳塞需要注意什么问题?

制作私模定制耳塞需要注意以下问题&#xff1a; 耳模制作&#xff1a;获取准确的耳模是制作私模定制耳塞的关键步骤。需要使用合适的材料和方法&#xff0c;确保耳模的准确性和稳定性。材料选择&#xff1a;选择合适的UV树脂和其它相关材料&#xff0c;确保它们的质量和性能符…

vue的网络请求以及封装

①先备好springboot的接口 ②安装依赖 在vue中安装网络请求工具的依赖&#xff1a; npm i axios③简单的demo 直接通过axios请求尝试一下&#xff1a; <script> import axios from "axios";export default {name: HomeView,data() {return {users:[]}}, …

第13章 网络 Page735~736 “I/O对象”的链式传递 计数器继承enable_shared_from_this<DownCounter>

使用enable_shared_from_this基类和该基类带来的shared_from_this()方法。DownCounter被加上基类enable_shared_from_this<T> 代码如下&#xff1a; 代码先通过shared_from_this()方法安全正确地复制智能指针counter&#xff0c;再通过lambda表达式以“捕获”的方式实现…

第20讲投票帖子排行实现

后端&#xff1a; /*** 投票选型Controller控制器* author java1234_小锋 &#xff08;公众号&#xff1a;java1234&#xff09;* site www.java1234.vip* company 南通小锋网络科技有限公司*/ RestController RequestMapping("/voteItem") public class VoteItemCo…

【C语言】指针练习篇(上),深入理解指针---指针和数组练习题和sizeof,strlen的对比【图文讲解,详细解答】

欢迎来CILMY23的博客喔&#xff0c;本期系列为【C语言】指针练习篇&#xff08;上&#xff09;&#xff0c;深入理解指针---指针数组练习题和sizeof&#xff0c;strlen的对比【图文讲解,详细解答】&#xff0c;图文讲解指针和数组练习题&#xff0c;带大家更深刻理解指针的应用…

【深入理解DETR】DETR的原理与算法实现

1 DETR算法概述 ①端到端 ②Transformer-model 之前的方法都需要进行NMS操作去掉冗余的bounding box或者手工设计anchor&#xff0c; 这就需要了解先验知识&#xff0c;增加从超参数anchor的数量&#xff0c; 1.1 训练测试框架 一次从图像中预测n个object的类别 训练阶段我们…

【PyQt】12-滑块、计数控件

文章目录 前言一、滑块控件 QSlider运行结果 二、计数器控件 QSpinBox运行结果 总结 前言 1、滑块控件 2、计数控件 一、滑块控件 QSlider #Author &#xff1a;susocool #Creattime:2024/2/15 #FileName:28-滑块控件 #Description: 通过滑块选择字体大小 import sys from PyQ…

基于 Python 深度学习的电影评论情感分析系统,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

Linux实用指令

Linux实用指令 1.指定运行级别 运行级别说明&#xff1a; 0 &#xff1a;关机 1 &#xff1a;单用户【找回丢失密码】 2&#xff1a;多用户状态没有网络服务 3&#xff1a;多用户状态有网络服务 4&#xff1a;系统未使用保留给用户 5&#xff1a;图形界面 6&#xff1a;系统重…

海量数据处理商用短链接生成器平台 - 3

第三章 商用短链平台实战-账号微服务流量包设计 第1集 账号微服务和流量包数据库表索引规范讲解 简介&#xff1a;账号微服务和流量包数据库表索引规范讲解 索引规范 主键索引名为 pk_字段名; pk即 primary key;唯一索引名为 uk_字段名&#xff1b;uk 即 unique key普通索引…

【C++航海王:追寻罗杰的编程之路】关于模板,你知道哪些?

目录 1 -> 泛型编程 2 -> 函数模板 2.1 -> 函数模板概念 2.2 -> 函数模板格式 2.3 -> 函数模板的原理 2.4 -> 函数模板的实例化 2.5 -> 函数参数的匹配原则 3 -> 类模板 3.1 -> 类模板的定义格式 3.2 -> 类模板的实例化 1 -> 泛型编…

C++:继承与派生基础

引入&#xff1a; 由自然界的动物繁衍的规律&#xff08;eg: 动物继承父类的一切属性&#xff0c;由父类派生并增加自己的新特征&#xff09;我们引入C语言在类的使用中描述此类问题。 为解决代码重复使用、提升效率&#xff0c;引入继承机制&#xff1a;允许保留原有类的特性…

Git快速掌握,通俗易懂

Git分布式版本控制工具 介绍 Git是一个开源的分布式版本控制系统&#xff0c;用于敏捷高效地处理任何或小或大的项目。Git是由Linus Torvalds为了帮助管理Linux内核开发而开发的一个开放源码的版本控制软件。Git可以帮助开发者们管理代码的版本&#xff0c;避免代码冲突&#…

ESP32学习(2)——点亮LED灯

1.前期准备 开发板原理图如下&#xff1a; 可见LED灯接在了GPIO2口 那么要如何编写代码控制GPIO口的电平高低呢&#xff1f; 我们可以参考micropython的官方文档Quick reference for the ESP32 — MicroPython latest documentation 可见&#xff0c;需要导入machine包 若要…

【教程】C++语言基础学习笔记(九)——指针

写在前面&#xff1a; 如果文章对你有帮助&#xff0c;记得点赞关注加收藏一波&#xff0c;利于以后需要的时候复习&#xff0c;多谢支持&#xff01; 【C语言基础学习】系列文章 第一章 《项目与程序结构》 第二章 《数据类型》 第三章 《运算符》 第四章 《流程控制》 第五章…

面向智算服务,构建可观测体系最佳实践

作者&#xff1a;蓟北 构建面向 AI、大数据、容器的可观测体系 &#xff08;一&#xff09;智算服务可观测概况 对于越来越火爆的人工智能领域来说&#xff0c;MLOps 是解决这一领域的系统工程&#xff0c;它结合了所有与机器学习相关的任务和流程&#xff0c;从数据管理、建…