当前位置: 首页 > news >正文

【分治法】线性时间选择问题

问题描述

给定线性序列中n个元素和一个整数k,1≤k≤n,要求在线性时间中找出这n个元素中第k小的元素

常规思路

常规思路是对序列先排序,落在第k个位置的元素就是第k小的元素。

这种方法的时间复杂度不是线性的,是O(nlogn)的时间复杂度,使用快排极端情况下甚至会出现O(n^2)的时间复杂度。问题需要在O(n)的时间内完成,故而这种方法不可行

快速排序的时间复杂度可以看这篇文章的最后

分治法解决

在这里插入图片描述

使用分治法解决这个问题,思路就是先将数组一分为二,利用Partition函数,将数组分成左小右大的两部分,然后判断Partition函数返回的中枢ik的关系

  • i<k,第k小在右数组,递归调用自身,在i+1r的区间中找第k-j
  • i>k,第k小在左数组,递归调用自身,在pi的区间中找第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&#xff0c;1≤k≤n&#xff0c;要求在线性时间中找出这n个元素中第k小的元素 常规思路 常规思路是对序列先排序&#xff0c;落在第k个位置的元素就是第k小的元素。 这种方法的时间复杂度不是线性的&#xff0c;是O(nlogn)的时间…...

SpringBoot速成(16)项目部署P30

部署是一个非常重要的环节。部署的目的是将开发完成的程序运行在服务器上&#xff0c;让其他用户或系统能够访问和使用它。 让程序对外提供服务 开发环境的局限性&#xff1a;开发环境通常是本地计算机&#xff0c;仅供开发人员使用。但实际应用需要让其他用户&#xff08;比如…...

【Mysql:数据库的基础操作】

目录 数据库创建&#xff0c;删除基础指令&#xff1a; 数据库的编码集&#xff1a; 数据库备份与恢复&#xff1a; 表的操作&#xff1a; 数据库创建&#xff0c;删除基础指令&#xff1a; show databases;//查看数据库列表//创建数据库 create database db_name; crea…...

Nacos Derby 远程命令执行漏洞修复建议

由于Nacos < 2.4.0 BETA 存在 Derby 远程命令执行漏洞&#xff0c;恶意攻击者利用此漏洞可以未授权执行SQL语句&#xff0c;最终导致任意代码执行。目前该漏洞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&#xff1b;”&#xff0c;键入一个字符&#xff0c;然后在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集群证书过期的做法 这个是很久之前遇到的了&#xff0c;今天有空&#xff08;心血来潮&#xff09;就都回忆回忆写在这里为爱发光&#xff0c;部分内容来自arch先生&#xff08;死党&#xff09;的帮助。有时候有很多部门提了建k8s的需求&#xff0c;有些是临…...

2024年河北省职业院校技能大赛网络系统管理赛项样题解法

​ 有问题请留言或主页私信咨询 2024年河北省职业院校技能大赛 网络系统管理赛项 网络构建 ​ ​ 目录 任务描述 任务清单 &#xff08;一&#xff09;基础配置 &#xff08;二&#xff09;有线网络配置 &#xff08;三&#xff09;无线网络配置 &#xff08;四&am…...

【开源免费】基于SpringBoot+Vue.JS个人博客系统(JAVA毕业设计)

本文项目编号 T 203 &#xff0c;文末自助获取源码 \color{red}{T203&#xff0c;文末自助获取源码} T203&#xff0c;文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...

纯新手教程:用llama.cpp本地部署DeepSeek蒸馏模型

0. 前言 llama.cpp是一个基于纯C/C实现的高性能大语言模型推理引擎&#xff0c;专为优化本地及云端部署而设计。其核心目标在于通过底层硬件加速和量化技术&#xff0c;实现在多样化硬件平台上的高效推理&#xff0c;同时保持低资源占用与易用性。 最近DeepSeek太火了&#x…...

JDK 8+新特性(Stream API、Optional、模块化等)

JDK 8新特性&#xff08;Stream API、Optional、模块化等&#xff09; 一、Stream API 1.1 概述 Stream API 是 Java 8 引入的一个新的抽象概念&#xff0c;它允许以声明式的方式处理数据集合。Stream 不是一个数据结构&#xff0c;而是对数据源&#xff08;如集合、数组等&…...

国产编辑器EverEdit - 独门暗器:自动监视剪贴板内容

1 监视剪贴板 1.1 应用场景 如果需要对剪贴板的所有历史进行记录&#xff0c;并进行分析和回顾&#xff0c;则可以使用监视剪贴板功能&#xff0c;不仅在EverEdit中的复制会记录&#xff0c;在其他应用的复制也会记录。 1.2 使用方法 新建一个空文档(重要&#xff1a;防止扰乱…...

贪心算法-买卖股票的最佳时机

买卖股票的最佳时机 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天 的价格。你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股 票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易…...

文本操作基础知识:正则表达式

目录 摘要&#xff1a; 一、语法 二、匹配模式pattern 1、普通字符[ ] 2、限定字符 3、定位字符 4、运算字符( ) 三、修饰符flags 四、各语言的正则使用 1、Python的re 参考资料&#xff1a; 摘要&#xff1a; 常用匹配&#xff1a;[A-C]、[^A-C]、\w、\d、\n、\r、…...

【Scrapy】Scrapy教程6——提取数据

前一小节我们拿到了页面的数据,那页面中那么多内容,我们想要其中的部分内容,该如何获取呢?这就需要对我们下载到的数据进行解析,提取出来想要的数据,这节就讲讲如何提取数据。 引入 我们编辑保存下来的shouye.html文件看下,发现这是什么鬼,全是如下图的代码。 没错…...

PHP 网络编程介绍

PHP 学习资料 PHP 学习资料 PHP 学习资料 在当今数字化时代&#xff0c;网络编程是开发各类应用必不可少的技能。PHP 作为一门广泛应用于 Web 开发的编程语言&#xff0c;同样具备强大的网络编程能力。接下来&#xff0c;我们将深入探讨 PHP 中网络连接的建立、Socket 编程、…...

【C语言】C语言 食堂自动化管理系统(源码+数据文件)【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;专__注&#x1f448;&#xff1a;专注主流机器人、人工智能等相关领域的开发、测试技术。 【C语言】C语言 食堂自动化管理系统&#xff08;源…...

mybatis存储过程返回list

在MyBatis中&#xff0c;要想通过调用存储过程返回一个List集合&#xff0c;你需要在Mapper接口中定义一个方法&#xff0c;并使用Param注解来传递存储过程的参数。同时&#xff0c;你需要在Mapper XML文件中配置相应的<select>标签&#xff0c;并指定statementType"…...

【vue】nodejs版本管理利器:nvm

nvm&#xff08;Node Version Manager&#xff09;即 Node 版本管理器&#xff0c;是一个用于在系统中轻松安装、管理和切换不同版本 Node.js 的工具。 在实际开发中&#xff0c;不同的项目可能基于不同版本的 Node.js 构建。比如一个旧项目依赖于 Node.js 12.x 版本的特定功能…...

负载测试工具有哪些?

Apache JMeter Apache JMeter 是一款开源的性能测试工具&#xff0c;主要用于对 Web 应用程序进行功能、负载和压力测试。JMeter 支持多种协议和技术&#xff0c;包括 HTTP, HTTPS, FTP 和 WebSocket 等。通过模拟大量并发用户访问来评估应用程序的表现1。 jmeter -n -t testp…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

Python常用模块:time、os、shutil与flask初探

一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...

node.js的初步学习

那什么是node.js呢&#xff1f; 和JavaScript又是什么关系呢&#xff1f; node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说&#xff0c; 需要在node.js的环境上进行当JavaScript作为前端开发语言来说&#xff0c;需要在浏览器的环境上进行 Node.js 可…...

向量几何的二元性:叉乘模长与内积投影的深层联系

在数学与物理的空间世界中&#xff0c;向量运算构成了理解几何结构的基石。叉乘&#xff08;外积&#xff09;与点积&#xff08;内积&#xff09;作为向量代数的两大支柱&#xff0c;表面上呈现出截然不同的几何意义与代数形式&#xff0c;却在深层次上揭示了向量间相互作用的…...