当前位置: 首页 > 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…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...