【AcWing-Python-786】第k个数/快速选择算法

news/2024/3/29 6:59:07/文章来源:https://blog.csdn.net/qq_43629945/article/details/129211783
题目:https://www.acwing.com/problem/content/788/
对应视频讲解:https://www.acwing.com/video/228/

题目描述


回顾快排

【AcWing-Python-785】快速排序 - CSDN博客

(一)步骤

  1. 找到分界点x:可以是区间最左端点、区间最右端点、或区间中点

  1. 将整个区间划分为两段,使得左边所有数Left ≤ x,右边所有数Right ≥ x【注意分界点位置的值不一定为x】

  1. 递归排序Left,递归排序Right

(二)时间复杂度

排序的时间复杂度是O(n * logn),快速排序的时间复杂度是O(n)

(三)与快选的联系

经过步骤1和2后,整个区间里,在分界点左边的数都≤x(假设长度为SL),右边的数都≥x(假设长度为SR)。现在想找到第k大的数

  • 若 k ≤ SL,则整个区间第k小的数一定在左边,此时只需递归处理左边即可

  • 若 k >SL,则整个区间第k小的数一定在右边,此时只需递归处理右边即可

快排需要递归左右两边,而快选只需要递归一边即可

快选的时间复杂度为O(n)

  • 先对整个区间划分两部分,使左边都≤x,右边都≥x,这步需要扫描整个区间n,故为O(n)

  • 根据第k小的数的k,与左边区间的长度SL的大小关系,判断是递归处理左边还是右边,只需扫描一半的区间即可,故为O(n/2)

  • 以此类推,n + n/2 + n/4 + n/8 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...) ≤ 2n,故为O(2n),因为常数不影响,故还是O(n)


解题思路及代码

(一)思路

首先明确,第k大的数X在有序数组中的位置为k-1(i ∈ [0, n-1])

采用快排分治思想,每次可只处理X所在的那一半区间,所以在进行快排找分界点时,找到此次递归的数组分界点j,将此次递归区间 [l, r] 分为 [l, j] 和 [j+1, r] 左右两个区间,并确定左右区间中的数,这些数在有序数组中也处于该区间,这样就可以根据j来确定k-1在左区间还是在右区间

  • 如果 k - 1 <= j,说明k - 1在左区间,则递归处理左区间,舍去(不处理)右区间

  • 反之如果k - 1 > j,说明k - 1在右区间,则递归处理右区间,舍去(不处理)左区间

不断递归,区间长度为1时,则找到了在有序数组中下标为k-1的数X

(二)代码

n, k = map(int, input().split())
nums = list(map(int, input().split()))def quick_sort(arr, left, right):if left >= right:returni, j, x = left-1, right+1, arr[(left+right)//2]while i < j:i += 1j -= 1while arr[i]<x:i += 1while arr[j]>x:j -= 1if i<j:arr[i], arr[j] = arr[j], arr[i]   # 此时j左边都是≤x的数,j右边都是≥x的数# 要找到排序后第k小的数,也即下标为 k-1 的数if k-1 <= j:quick_sort(arr, left, j)if k-1 > j:quick_sort(arr, j+1, right)quick_sort(nums, 0, n-1)
print(nums[k-1])

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

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

相关文章

华为OD机试用Python实现 -【天然蓄水库 or 天然蓄水池】(2023-Q1 新题)

华为OD机试题 华为OD机试300题大纲天然蓄水库 or 天然蓄水池题目描述输入描述输出描述说明示例一输入输出说明示例二输入输出说明示例三输入输出说明Python 代码实现算法思路华为OD机试300题大纲 参加华为

蓝桥2.24训练

1&#xff0c;奇怪的函数 P2759 奇怪的函数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 1这道题有两个点&#xff0c;一个是求数的位数 2&#xff0c;用整数二分求出的位数与n比较 #include <bits/stdc.h> using namespace std; typedef long long ll; ll n; int ma…

这9道软件测试面试题,就能刷掉90%的软件测试员

转眼就要到“金三银四”了&#xff0c;没点真本事真技术&#xff0c;没点面试经验&#xff0c;不了解点职场套路&#xff0c;如何过五关斩六将&#xff1f;如何打败面试官&#xff1f;如何拿下那梦寐以求的offer&#xff1f; 如果你的跳槽意向已经很确定&#xff0c;那么请往下…

Laravel框架01:composer和Laravel简介

Laravel框架01&#xff1a;composer和Laravel简介一、Composer介绍二、创建Laravel项目三、Laravel目录结构四、Laravel启动方式一、Composer介绍 composer 是PHP中用来管理依赖关系的工具。类似于Javascript的NPM。composer官网&#xff1a;https://getcomposer.org/安装结束…

Android源码分析 —— Activity栈管理(基于Android8)

0. 写在前面 本文基于 Android8.0源码&#xff0c;和Android9.0大同小异&#xff0c;但和Android10.0差别非常大&#xff01;新版改用ATM来管理Activity的启动&#xff0c;Activity的生命周期也通过XXXItem来管理。由于我分析的Activity启动流程就是基于Android8/9的&#xff…

通用信息抽取技术UIE产业案例解析,Prompt 范式落地经验分享!

想了解用户的评价究竟是“真心夸赞”还是“阴阳怪气”&#xff1f;想快速从多角色多事件的繁杂信息中剥茧抽丝提取核心内容&#xff1f;想通过聚合相似事件准确地归纳出特征标签&#xff1f;……想了解UIE技术在产业中的实战落地经验&#xff1f;通用信息抽取技术 UIE 产业案例…

啊哈 算法读书笔记 第 2 章 栈、队列、链表

第 2 章 栈、队列、链表 目录 第 2 章 栈、队列、链表 队列&#xff1a; 解密回文——栈 纸牌游戏&#xff1a; 链表 模拟链表 队列&#xff1a; 首先将第 1 个数删除&#xff0c;紧接着将第 2 个数放到这串数的末尾&#xff0c;再将第 3 个数删除并将第 4 个数放到这串…

Mysql 语句优化 (Explain)

Mysql 语句优化 &#xff08;Explain&#xff09; 1. 概述 ​ 在 select 语句之前增加 explain 关键字&#xff0c; mysql 会在查询上设置一个标记&#xff0c;返回查询执行计划信息&#xff0c;而不是执行这条sql 字段formatjson时的名称含义idselect_id该语句的唯一标识sel…

centos7安装

centos7安装制作U盘启动盘下载镜像下载 UltralISO制作启动盘使用U盘安装系统修改模式为 UEFI调整BOOT option保存重启进入安装界面安装图形界面安装搜狗输入法制作U盘启动盘 下载镜像 去官网下载镜像&#xff0c;找到 mirrors链接&#xff08;速度快&#xff09; 选择一个中…

创客匠人直播:构建公域到私域的用户增长模型

进入知识付费直播带货时代&#xff0c;很多拥有知识技能经验的老师和培训机构吃到了流量红利。通过知识付费直播&#xff0c;老师们可以轻松实现引流、变现&#xff0c;还可以突破时间、地域的限制&#xff0c;为全国各地的学员带来优质的教学服务&#xff0c;因此越来越受到教…

使用JavaScript+Selenium玩转Web应用自动化测试

自动化测试 在软件开发过程中, 测试是功能验收的必要过程, 这个过程往往有测试人员参与, 提前编写测试用例, 然后再手动对测试用例进行测试, 测试用例都通过之后则可以认为该功能通过验收. 但是软件中多个功能之间往往存在关联或依赖关系, 某一个功能的新增或修改可能或影响到…

CTFer成长之路之反序列化漏洞

反序列化漏洞CTF 1.访问url&#xff1a; http://91a5ef16-ff14-4e0d-a687-32bdb4f61ecf.node3.buuoj.cn/ 点击下载源码 本地搭建环境并访问url&#xff1a; http://127.0.0.1/www/public/ 构造payload&#xff1a; ?sindex/index/hello&ethanwhoamiPOST的参数&#…

Redis的持久化方式

Redis支持两种方式的持久化&#xff0c;一种是RDB方式、另一种是AOF&#xff08;append-only-file&#xff09;方式&#xff0c;两种持久化方式可以单独使用其中一种&#xff0c;也可以将这两种方式结合使用。 •RDB&#xff1a;根据指定的规则“定时”将内存中的数据存储在硬…

【Virtualization】Windows11安装VMware Workstation后异常处置

安装环境 Windows 11 专业版 22H2 build 22621.1265 VMware Workstation 17 Pro 17.0.0 build-20800274 存在问题 原因分析 1、BIOS未开启虚拟化。 2、操作系统启用的虚拟化与Workstation冲突。 3、操作系统启用内核隔离-内存完整性保护。 处置思路 1、打开“资源管理器”…

6-Java中新建一个文件、目录、路径

文章目录前言1-文件、目录、路径2-在当前路径下创建一个文件3-在当前路径下创建一个文件夹&#xff08;目录&#xff09;3.1 测试1-路径已经存在3.2 测试2-路径不存在3.2 创建不存在的路径并新建文件3.3 删除已存在的文件并新建4-总结前言 学习Java中如何新建文件、目录、路径…

Fiddler报文分析-断点应用、模拟网络限速-HTTPS的 拦截

目录 一、报文分析 Statistics 请求性能数据 检查器&#xff08;Inspectors&#xff09; 自定义响应&#xff08;AutoResponder&#xff09; Composer Composer的功能就是用来创建HTTP Request然后发送请求。 允许自定义请求发送到服务器&#xff0c;即可以手动创建一个新…

大学毕业后,送了2个月外卖,哭了一整晚

先简单介绍一下自己&#xff0c;我来自湛江&#xff0c;大学学的的物流管理专业&#xff0c;现在就职于一家互联网公司&#xff0c;从事软件测试工作。 我来自湛江的一个偏远农村&#xff0c;家里兄弟姐妹多&#xff0c;父母无力负担我的学费&#xff0c;很多时候学费都是靠姐…

CHATGPT是新的“搜索引擎终结者”吗?百度是否慌了

ChatGPT 以其非凡的自然语言处理 &#xff08;NLP&#xff09; 能力和清晰的响应风靡全球&#xff0c;有望带来一场重大的技术革命。在不知不觉中&#xff0c;叙事转向了ChatGPT与百度的对决&#xff0c;因为来自OpenAI的智能和健谈的聊天机器人已经慢慢获得了“潜在的百度终结…

JS 执行机制 详解(附图)

一、JS是单线程JS语言的一大特点就是单线程&#xff0c;也就是说&#xff0c;同一个时间只能做一件事。这是JS这门脚本语言诞生的使命所致——用来处理页面中用户的交互&#xff0c;以及操作DOM而诞生的。单线程就意味着&#xff0c;所有任务需要排队&#xff0c;前一个任务结束…

自动化测试整理 --- STAF/STAX Robot Framework

题记:上周花了点时间学习开源的自动化测试框架Robot Framework,结合自己之前的自动化经验&#xff0c;就想周末写篇文章整理下。 目前&#xff0c;所在项目的自动化测试框架是基于STAF/STAX的拓展&#xff0c;围绕STAX执行引擎&#xff0c;扩展了测试用例的创建、管理&#xf…