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

线性时间选择

给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素
#include<iostream>
#include<cstdlib>
#include<time.h>
using namespace std;
int a[100];
int Random(int left,int right)
{srand(time(NULL));return rand()%(right-left+1)+left;
}
int PartSort(int left,int right)
{int key=Random(left,right);swap(a[left],a[key]);while(left<right){while(left<right&&a[right]>=a[key])right--;while(left<right&&a[left]<=a[key])left++;if(left<right)swap(a[left],a[right]);}swap(a[key],a[left]);return left;
}
int RandomizedSelect(int left,int right,int k)
{if(left==right)return a[left];int key=PartSort(left,right);int j=key-left+1;if(j==k)return a[key];if(k<j)return RandomizedSelect(left,key,k);elsereturn RandomizedSelect(key+1,right,k-j);}
int main()
{int n,k;cin>>n>>k;for(int i=0;i<n;i++)cin>>a[i];cout<<RandomizedSelect(0,n-1,k)<<endl;return 0;
}

相关文章:

线性时间选择

给定线性序集中n个元素和一个整数k&#xff0c;1≤k≤n&#xff0c;要求找出这n个元素中第k小的元素 #include<iostream> #include<cstdlib> #include<time.h> using namespace std; int a[100]; int Random(int left,int right) {srand(time(NULL));return …...

【对算法期中卷子的解析和反思】

一、程序阅读并回答问题&#xff08;共30分&#xff09; #include<cstdio>#include<cstring>#include<iostream>using namespace std;char chess[10][10];int sign[10];int n, k, ans;void dfs(int x, int k) { if (k 0){ans;return; } if (xk-1 >…...

sudo apt update sudo: apt: command not found

CentOS或RHEL&#xff08;Red Hat Enterprise Linux&#xff09;系统上&#xff0c;包管理器是yum或dnf&#xff0c;而不是apt。您可以使用yum或dnf来安装软件包。以下是如何在CentOS或RHEL上安装Git的详细步骤&#xff1a; 1. 使用yum安装Git 首先&#xff0c;更新软件包列表&…...

ios:文本框默认的copy、past改成中文复制粘贴

问题 ios 开发&#xff0c;对于输入框的一些默认文案展示&#xff0c;如复制粘贴是英文的&#xff0c;那么如何改为中文的呢 解决 按照路径找到这个文件 ios/项目/Info.plist&#xff0c;增加 <key>CFBundleAllowMixedLocalizations</key> <true/> <…...

Qt moc系统的黑魔法?

Qt的元对象系统&#xff08;Meta-Object System&#xff09;是Qt框架的核心功能之一&#xff0c;为C语言增加了一些动态特性&#xff0c;借助元对象系统Qt可以实现以下功能 信号与槽机制&#xff08;Signals and Slots&#xff09;运行时类型信息&#xff08;Run-Time Type In…...

MyBatis开发中常用总结

文章目录 常用MyBatis参数映射单个参数多个参数使用索引【不推荐】Param注解Map传参POJO【推荐】List数组 动态标签\<if>标签\<trim>标签\<where>标签\<set>标签\<foreach>标签 MyBatis查询一对一一对多 常用MyBatis参数映射 单个参数 XML中可…...

Git基本使用教程(学习记录)

参考文章链接&#xff1a; Git教程&#xff08;超详细&#xff0c;一文秒懂&#xff09; RUNOOB Git教程 Git学习记录 1Git概述 1.1版本控制软件功能 版本管理&#xff1a;更新或回退到历史上任何版本&#xff0c;数据备份共享代码&#xff1a;团队间共享代码&#xff0c;…...

【Linux-RTC】

Linux-RTC ■ rtc_device 结构体■ RTC 时间查看与设置■ 1、时间 RTC 查看■ 2、设置 RTC 时间 ■ rtc_device 结构体 Linux 内核将 RTC 设备抽象为 rtc_device 结构体 rtc_device 结构体&#xff0c;此结构体定义在 include/linux/rtc.h 文件中 ■ RTC 时间查看与设置 ■ 1…...

机器学习目录

文章目录 基本概念有监督学习回归问题分类问题 无监督学习聚类问题异常检测 基本概念 pass 有监督学习 回归问题 通过拟合函数&#xff0c;解决连续值的预测问题梯度下降法优化&#xff1b;最小二乘法求解&#xff1b;度量指标 均方误差&#xff1b;均方根误差&#xff1b;平…...

React开发环境配置详细讲解-04

环境简介 前端随着规范化&#xff0c;可以说规范和环境插件配置满天飞&#xff0c;笔者最早接触的是jquery&#xff0c;那个开发非常简单&#xff0c;只要引入jquery就可以了&#xff0c;当时还写了一套UI框架&#xff0c;至今在做小型项目中还在使用&#xff0c;show一张效果…...

Go 如何通过 Kafka 客户端库 生产与消费消息

文章目录 0.前置说明1. confluent-kafka-go2. sarama3. segmentio/kafka-go4. franz-go选择建议 1.启动 kafka 集群2.安装 confluent-kafka-go 库3.创建生产者特殊文件说明如何查看.log文件内容 4.创建消费者 0.前置说明 Go 语言中有一些流行的 Kafka 客户端库。以下是几个常用…...

【设计模式深度剖析】【B】【结构型】【对比】| 主要区别包装的不同

&#x1f448;️上一篇:享元模式 回 顾&#xff1a;结构型设计模式 1.代理模式&#x1f448;️ 2.装饰器模式&#x1f448;️ 3.适配器模式&#x1f448;️ 4.组合模式&#x1f448;️ 5.桥接模式&#x1f448;️ 6.外观模式&#x1f448;️ 7.享元模式&#x…...

信息学奥赛初赛天天练-17-阅读理解-浮点数精准输出与海伦公式的巧妙应用

PDF文档公众号回复关键字:20240531 1 2023 CSP-J 阅读程序1 阅读程序&#xff08;程序输入不超过数组成字符串定义的范围&#xff1a;判断题正确填√&#xff0c;错误填&#xff1b;除特殊说明外&#xff0c;判断题1.5分&#xff0c;选择题3分&#xff0c;共计40分&#xff0…...

mysql - 为什么MySQL不建议使用NULL作为列默认值?

为什么MySQL不建议使用NULL作为列默认值&#xff1f; InnoDB有4中行格式&#xff1a; Redundant : 非紧凑格式,5.0 版本之前用的行格式,目前很少使用,Compact : 紧凑格式,5.1 版本之后默认行格式,可以存储更多的数据Dynamic , Compressed : 和Compact类似,5.7 版本之后默认使…...

数据分析案例-在线食品订单数据可视化分析与建模分类

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…...

构建LangChain应用程序的示例代码:2、使用LangChain库实现的AutoGPT示例:查找马拉松获胜成绩

AutoGPT 示例&#xff1a;查找马拉松获胜成绩 实现 https://github.com/Significant-Gravitas/Auto-GPT&#xff0c;使用LangChain基础组件&#xff08;大型语言模型(LLMs)、提示模板(PromptTemplates)、向量存储(VectorStores)、嵌入(Embeddings)、工具(Tools)&#xff09;。…...

代码随想录算法训练营第三十四 |● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果

今天的解析写在了代码注释中 1005.K次取反后最大化的数组和 讲解链接&#xff1a;https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html class Solution { public:static bool cmp(i…...

GB-T 43206-2023 信息安全技术 信息系统密码应用测评要求

GB-T 43206-2023 信息安全技术 信息系统密码应用测评要求 编写背景 随着信息技术的飞速发展&#xff0c;信息系统在社会经济活动中扮演着越来越重要的角色。信息安全问题也随之成为社会关注的焦点。GB-T 43206-2023《信息安全技术 信息系统密码应用测评要求》是针对信息系统中…...

线程进阶-1 线程池

一.说一下线程池的执行原理 1.线程池的七大核心参数 &#xff08;1&#xff09;int corePoolSize&#xff1a;核心线程数。默认情况下核心线程会一直存活&#xff0c;当设置allowCoreThreadTimeout为true时&#xff0c;核心线程也会被超时回收。 &#xff08;2&#xff09;i…...

LabVIEW中PID控制器系统的噪声与扰动抑制策略

在LabVIEW中处理PID控制器系统中的噪声和外部扰动&#xff0c;需要从信号处理、控制算法优化、硬件滤波和系统设计四个角度入手。采用滤波技术、调节PID参数、增加前馈控制和实施硬件滤波器等方法&#xff0c;可以有效减少噪声和扰动对系统性能的影响&#xff0c;提高控制系统的…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...