线性时间选择

给定线性序集中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);
    else
        return 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;
}

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

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

相关文章

微客云霸王餐v3版本正式上线 团购霸王餐+小程序多开

好久没发布更新日志了&#xff0c;上次的更新还是春节的祝福语&#xff0c;从春节结束到现在快3个月了&#xff0c;不是说没更新内容&#xff0c;其实微客云的版本迭代一直在做&#xff0c;从后台的日志看已经发布很多版本了&#xff0c;只是没有发布文章通知&#xff0c;因为我…

算法(十二)分治算法

文章目录 算法概念算法例子字符串中小写转大写求X^n问题 算法概念 分治算法&#xff08;divide and conquer&#xff09;算法的核心思想其实就是"分而治之"&#xff0c;将原问题划分成n个规模较小&#xff0c;并且结构与原问题相似的子问题&#xff0c;递归地解决这…

鸿蒙工程目录介绍

鸿蒙构建完毕生成hhvp文件。 项目结构&#xff1a; .hvigor : 是存储构建配置文件的 .idea : 是开发工具拥有的目录 AppScope : 是全局的公共资源存放位置 hvigor &#xff1a;存放前端构建配置信息 oh_modules : 存放项目用到的第三方包 build-profile.json5 : 应用级别的构…

【MySQL数据库】:MySQL复合查询

目录 基本查询回顾 多表查询 自连接 子查询 单行子查询 多行子查询 多列子查询 在from子句中使用子查询 合并查询 前面我们讲解的mysql表的查询都是对一张表进行查询&#xff0c;在实际开发中这远远不够。 基本查询回顾 【MySQL数据库】&#xff1a;MySQL基本查…

华为telnet的两种认证方式

华为telnet的两种认证方式 实验拓扑&#xff1a; 实验要求&#xff1a; 1.采用普通密码认证实现telnet 远程登录机房设备R3 2.采用AAA认证服务方式实现telnet 远程登录机房设备R3 实验步骤&#xff1a; 1.完成基本配置&#xff08;设备接口配置IP&#xff0c;此步骤略过&#…

JVM-JAVA-类加载过程

JVM源码 类加载到 JVM 的过程通过 java 命令执行代码的流程 类加载到 JVM 的过程 在运行一个 main 函数启动程序是&#xff0c;首先需要类加载起把主类加载到 JVM 中 通过 java 命令执行代码的流程 loadClass的类加载过程有如下几步&#xff1a; 类被加载到方法区中后主要包…

视频汇聚EasyCVR安防系统对接公安部GA/T 1400视图库布控、告警、订阅流程描述

随着信息技术的飞速发展&#xff0c;视频监控在公共安全领域的应用越来越广泛&#xff0c;对于视频监控系统的要求也日益严格。为了满足公安系统对视频图像信息应用的高标准需求&#xff0c;视频汇聚平台EasyCVR视频监控系统全面支持GA/T 1400标准协议&#xff0c;为公安部门提…

【C++】——string模拟实现

前言 string的模拟实现其实就是增删改查&#xff0c;只不过加入了类的概念。 为了防止与std里面的string冲突&#xff0c;所以这里统一用String。 目录 前言 一 初始化和销毁 1.1 构造函数 1.2 析构函数 二 迭代器实现 三 容量大小及操作 四 运算符重载 4.1 bool…

03-树3 Tree Traversals Again(浙大数据结构PTA习题)

03-树3 Tree Traversals Again 分数 25 作者 陈越 An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, th…

实际测试stm32中断优先级

https://m.weibo.cn/1711020180/5040208380168258

【字典树(前缀树) 哈希映射 后序序列化】1948. 删除系统中的重复文件夹

本文涉及知识点 字典树&#xff08;前缀树) 哈希映射 后序序列化 LeetCode 1948. 删除系统中的重复文件夹 由于一个漏洞&#xff0c;文件系统中存在许多重复文件夹。给你一个二维数组 paths&#xff0c;其中 paths[i] 是一个表示文件系统中第 i 个文件夹的绝对路径的数组。 …

Codeforces Round 949 (Div. 2) (A~C)

1981A - Turtle and Piggy Are Playing a Game 贪心&#xff0c;每次取x 2&#xff0c;求最大分数 // Problem: B. Turtle and an Infinite Sequence // Contest: Codeforces - Codeforces Round 949 (Div. 2) // URL: https://codeforces.com/contest/1981/problem/B // Me…

iOS组件化 方案 实现

iOS组件化 组件化的原因现在流行的组件化方案方案一、url-block &#xff08;基于 URL Router&#xff09;方案二、protocol调用方式解读 方案三、target-action调用方式解读 gitHub代码链接参考 组件化的原因 模块间解耦模块重用提高团队协作开发效率单元测试 当项目App处于…

2024最新群智能优化算法:大甘蔗鼠算法(Greater Cane Rat Algorithm,GCRA)求解23个函数,提供MATLAB代码

一、大甘蔗鼠算法 大甘蔗鼠算法&#xff08;Greater Cane Rat Algorithm&#xff0c;GCRA&#xff09;由Jeffrey O. Agushaka等人于2024年提出&#xff0c;该算法模拟大甘蔗鼠的智能觅食行为。 参考文献 [1]Agushaka J O, Ezugwu A E, Saha A K, et al. Greater Cane Rat Alg…

LAMMPS - 分子动力学模拟器

本文翻译自&#xff1a;https://www.lammps.org/ 文章目录 一、关于 LAMMPS下载作者R&D 100 二、LAMMPS 亮点毛细血管中的血流 一、关于 LAMMPS 官网&#xff1a; https://www.lammps.org/ github &#xff1a;https://github.com/lammps/lammps LAMMPS 分子动力学模拟器…

初识java——javaSE(8)异常

文章目录 一 异常的概念与体系结构1.1 什么是异常&#xff1f;1.2 异常的体系结构&#xff01;1.3 编译时异常与运行时异常与Error编译时异常&#xff1a;异常声明&#xff1a;throws关键字 运行时异常&#xff1a;什么是Error? 二 处理异常2.1 异常的抛出&#xff1a;throw(注…

利用映射算子打印菱形

文章目录 一、利用RDD完成&#xff08;一&#xff09;右半菱形&#xff08;二&#xff09;左半菱形&#xff08;三&#xff09;完整菱形&#xff08;四&#xff09;输出任意大菱形 二、利用Java完成&#xff08;一&#xff09;右半菱形&#xff08;二&#xff09;左半菱形&…

恒压频比开环控制系统Matlab/Simulink仿真分析(SPWM控制方式)

介绍恒压频比的开环控制方法驱动永磁同步电机的转动&#xff0c;首先分析恒压频比的控制原理&#xff0c;然后在Matlab/Simulink中进行永磁同步电机恒压频比开环控制系统的仿真分析&#xff0c;最后将Simulink中的恒压频比控制算法生成代码加载到实际工程中进行工程实现。 一、…

react 表格实现拖拽功能

项目背景 : react ant 单纯实现拖拽确实不难 , 我的需求是根据后台接口返回 , 生成对应的父子表格 , 并只可以拖拽子的位置 , 如图 后台返回的数据结构 (pid为0说明是父 , 子的pid等于父的id , 说明是父的子) 1 , 我先转成了树形结构且自己加上了key (注意 : key一定得是唯一的…

异常(Exception)

捕获异常 public class test {public static void main(String [] args) {int[] arr {1,2,3,4,5};try {System.out.println(arr[10]);}catch (ArrayIndexOutOfBoundsException e) {//索引越界异常System.out.println("索引越界");}System.out.println("看看我是…