【分治法】线性时间选择问题
问题描述
给定线性序列中n个元素和一个整数k,1≤k≤n,要求在线性时间中找出这n个元素中第k小的元素
常规思路
常规思路是对序列先排序,落在第k个位置的元素就是第k小的元素。
这种方法的时间复杂度不是线性的,是O(nlogn)的时间复杂度,使用快排极端情况下甚至会出现O(n^2)的时间复杂度。问题需要在O(n)的时间内完成,故而这种方法不可行
快速排序的时间复杂度可以看这篇文章的最后
分治法解决

使用分治法解决这个问题,思路就是先将数组一分为二,利用Partition函数,将数组分成左小右大的两部分,然后判断Partition函数返回的中枢i与k的关系
i<k,第k小在右数组,递归调用自身,在i+1到r的区间中找第k-j小i>k,第k小在左数组,递归调用自身,在p到i的区间中找第k小i==k,当前值就是第k小
递归边界是p=r时,数组只有一个元素,第一小第k小都是该元素
代码
Type RandomizedSelect(Type a[], int p, int r, int k) {if (p == r)return a[p];i = RandomizedPartition(a, p, r);j = i - p + 1;if (k == j)return a[i];else if (k < j)return RandomizedSelect(a, p, i, k);elsereturn RandomizedSelect(a, i + 1, r, k - j);
}
Type RandomizedPartition(Type a[], int p, int r) {i = Random(p, r);//用于生成p到r的随机数swap(a[i], a[p]);//交换a[i]和a[p]return Partition(a, p, r);
}
关于Partition算法,可以看这篇文章中的介绍
由于Partition算法存在的不足,故而这里使用RandomizedPartition算法,随机选择一个元素作为划分基准,效果更好
算法分析
极端情况下,算法的最坏时间复杂度仍是 O ( n 2 ) O(n^2) O(n2),尽管使用RandomizedPartition算法,仍不难保证极端情况的绝对不发生
但可以证明,算法的平均时间复杂度是 O ( n ) O(n) O(n)的
相关文章:
【分治法】线性时间选择问题
问题描述 给定线性序列中n个元素和一个整数k,1≤k≤n,要求在线性时间中找出这n个元素中第k小的元素 常规思路 常规思路是对序列先排序,落在第k个位置的元素就是第k小的元素。 这种方法的时间复杂度不是线性的,是O(nlogn)的时间…...
SpringBoot速成(16)项目部署P30
部署是一个非常重要的环节。部署的目的是将开发完成的程序运行在服务器上,让其他用户或系统能够访问和使用它。 让程序对外提供服务 开发环境的局限性:开发环境通常是本地计算机,仅供开发人员使用。但实际应用需要让其他用户(比如…...
【Mysql:数据库的基础操作】
目录 数据库创建,删除基础指令: 数据库的编码集: 数据库备份与恢复: 表的操作: 数据库创建,删除基础指令: show databases;//查看数据库列表//创建数据库 create database db_name; crea…...
Nacos Derby 远程命令执行漏洞修复建议
由于Nacos < 2.4.0 BETA 存在 Derby 远程命令执行漏洞,恶意攻击者利用此漏洞可以未授权执行SQL语句,最终导致任意代码执行。目前该漏洞PoC和技术细节已在互联网上公开。 一、漏洞情况分析 Nacos 是一个功能强大的服务注册与发现、配置管理平台&#…...
idea 2023.3.7常用插件
idea 2023.3.7常用插件 文档 idea 2019.3常用插件idea 2023.3.7常用插件 idea 2023.3.7常用插件 插件名称插件版本说明1AceJump3.5.9AceJump允许您快速将插入符号导航到编辑器中可见的任何位置。只需按“ctrl;”,键入一个字符,然后在Ace …...
DeepSeek和ChatGPT在科研课题设计和SCI论文写作中的应用
DeepSeek和ChatGPT在科研课题设计和SCI论文写作中的应用 一、DeepSeek和ChatGPT的基础理论 (理论讲解案例分析) 1.DeepSeek的技术架构 (1)DeepSeek的定义与核心目标 (2)DeepSeek的主要类型 如DeepSeek-R1、DeepSeek-V3等 (3)DeepSeek的主要创新点、优势能力以及主要应用场景 2.…...
kubeadm拉起的k8s集群证书过期的做法集群已奔溃也可以解决
kubeadm拉起的k8s集群证书过期的做法 这个是很久之前遇到的了,今天有空(心血来潮)就都回忆回忆写在这里为爱发光,部分内容来自arch先生(死党)的帮助。有时候有很多部门提了建k8s的需求,有些是临…...
2024年河北省职业院校技能大赛网络系统管理赛项样题解法
有问题请留言或主页私信咨询 2024年河北省职业院校技能大赛 网络系统管理赛项 网络构建 目录 任务描述 任务清单 (一)基础配置 (二)有线网络配置 (三)无线网络配置 (四&am…...
【开源免费】基于SpringBoot+Vue.JS个人博客系统(JAVA毕业设计)
本文项目编号 T 203 ,文末自助获取源码 \color{red}{T203,文末自助获取源码} T203,文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...
纯新手教程:用llama.cpp本地部署DeepSeek蒸馏模型
0. 前言 llama.cpp是一个基于纯C/C实现的高性能大语言模型推理引擎,专为优化本地及云端部署而设计。其核心目标在于通过底层硬件加速和量化技术,实现在多样化硬件平台上的高效推理,同时保持低资源占用与易用性。 最近DeepSeek太火了&#x…...
JDK 8+新特性(Stream API、Optional、模块化等)
JDK 8新特性(Stream API、Optional、模块化等) 一、Stream API 1.1 概述 Stream API 是 Java 8 引入的一个新的抽象概念,它允许以声明式的方式处理数据集合。Stream 不是一个数据结构,而是对数据源(如集合、数组等&…...
国产编辑器EverEdit - 独门暗器:自动监视剪贴板内容
1 监视剪贴板 1.1 应用场景 如果需要对剪贴板的所有历史进行记录,并进行分析和回顾,则可以使用监视剪贴板功能,不仅在EverEdit中的复制会记录,在其他应用的复制也会记录。 1.2 使用方法 新建一个空文档(重要:防止扰乱…...
贪心算法-买卖股票的最佳时机
买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天 的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股 票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易…...
文本操作基础知识:正则表达式
目录 摘要: 一、语法 二、匹配模式pattern 1、普通字符[ ] 2、限定字符 3、定位字符 4、运算字符( ) 三、修饰符flags 四、各语言的正则使用 1、Python的re 参考资料: 摘要: 常用匹配:[A-C]、[^A-C]、\w、\d、\n、\r、…...
【Scrapy】Scrapy教程6——提取数据
前一小节我们拿到了页面的数据,那页面中那么多内容,我们想要其中的部分内容,该如何获取呢?这就需要对我们下载到的数据进行解析,提取出来想要的数据,这节就讲讲如何提取数据。 引入 我们编辑保存下来的shouye.html文件看下,发现这是什么鬼,全是如下图的代码。 没错…...
PHP 网络编程介绍
PHP 学习资料 PHP 学习资料 PHP 学习资料 在当今数字化时代,网络编程是开发各类应用必不可少的技能。PHP 作为一门广泛应用于 Web 开发的编程语言,同样具备强大的网络编程能力。接下来,我们将深入探讨 PHP 中网络连接的建立、Socket 编程、…...
【C语言】C语言 食堂自动化管理系统(源码+数据文件)【独一无二】
👉博__主👈:米码收割机 👉技__能👈:C/Python语言 👉专__注👈:专注主流机器人、人工智能等相关领域的开发、测试技术。 【C语言】C语言 食堂自动化管理系统(源…...
mybatis存储过程返回list
在MyBatis中,要想通过调用存储过程返回一个List集合,你需要在Mapper接口中定义一个方法,并使用Param注解来传递存储过程的参数。同时,你需要在Mapper XML文件中配置相应的<select>标签,并指定statementType"…...
【vue】nodejs版本管理利器:nvm
nvm(Node Version Manager)即 Node 版本管理器,是一个用于在系统中轻松安装、管理和切换不同版本 Node.js 的工具。 在实际开发中,不同的项目可能基于不同版本的 Node.js 构建。比如一个旧项目依赖于 Node.js 12.x 版本的特定功能…...
负载测试工具有哪些?
Apache JMeter Apache JMeter 是一款开源的性能测试工具,主要用于对 Web 应用程序进行功能、负载和压力测试。JMeter 支持多种协议和技术,包括 HTTP, HTTPS, FTP 和 WebSocket 等。通过模拟大量并发用户访问来评估应用程序的表现1。 jmeter -n -t testp…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
