AcWing 786. 第k个数——算法基础课题解

news/2024/6/15 14:54:29/文章来源:https://blog.csdn.net/m0_63230155/article/details/137346055

AcWing 786. 第k个数

题目描述

给定一个长度为 n的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数(所有整数均在 1∼10^9 范围内),表示整数数列。

输出格式

输出一个整数,表示数列的第 k 小数。

数据范围

1≤n≤100000,

1≤k≤n

输入样例:

5 3
2 4 1 5 3

输出样例:

3
思路

image-20240403110228271

C++
#include <iostream>using namespace std;const int N = 1e5 + 10;int quick_sort(int q[], int l, int r, int k) {if (l == r) return q[l];int i = l - 1, j = r + 1, x = q[(l + r) >> 1];while (i < j) {while (q[++i] < x);while (q[--j] > x);if (i < j) swap(q[i], q[j]);}int sl = j - l + 1;if (k <= sl) return quick_sort(q, l, j, k);else return quick_sort(q, j + 1, r, k - sl);
}int main() {int n, k;cin >> n >> k;int q[N];for (int i = 0; i < n; i++) cin >> q[i];cout << quick_sort(q, 0, n - 1, k) << endl;return 0;
}
Go
package mainimport "fmt"func quickSort(arr []int, left int, right int, k int) int {if left == right {return arr[left]}i := left - 1j := right + 1x := arr[(left+right)>>1]for i < j {for {i++if arr[i] >= x {break}}for {j--if arr[j] <= x {break}}if i < j {arr[i], arr[j] = arr[j], arr[i]}}sl := j - left + 1if sl >= k {return quickSort(arr, left, j, k)} else {return quickSort(arr, j+1, right, k-sl)}
}func main() {var n, k intfmt.Scanf("%d", &n)fmt.Scanf("%d", &k)arr := make([]int, n)for i := 0; i < n; i++ {fmt.Scanf("%d", &arr[i])}fmt.Println(quickSort(arr, 0, n-1, k))
}

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

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

相关文章

函数参数缺省和内联函数【C++】

文章目录 函数参数缺省函数参数缺省的条件和要求 内联函数内联函数的工作原理内联函数的定义方法内联函数的要求解决方法&#xff1a;直接在.h中定义内联函数的函数体 内联函数再Debug模式下默认是不展开的 函数参数缺省 顾名思义&#xff1a;可以少传一个/多个参数给函数&…

Stream 流和 Lambda 组装复杂父子树形结构

在最近的开发中&#xff0c;遇到了两个类似的需求&#xff1a;都是基于 Stream 的父子树形结构操作&#xff0c;返回 List 集合对象给前端。于是在经过需求分析和探索实践后有了新的认识&#xff0c;现在拿出来和大家作分享交流。 一般来说完成这样的需求大多数人会想到递归&a…

金融汽车科技LLM

汇丰银行 众安保险 1. AIGC重塑保险价值链 小额高频 2.构建智能应用的技术方案演进 增加微服务 长记忆&#xff1a;向量库短记忆&#xff1a;对话历史&#xff0c;思考路径&#xff0c;执行历史 中台架构设计 蔚来汽车在大模型的应用实践 公司介绍 应用架构 应用实践 4.大…

数据结构 - 算法效率|时间复杂度|空间复杂度

目录 1.算法效率 2.时间复杂度 2.1定义 2.2大O渐近表示法 2.3常见时间复杂度计算举例 3.空间复杂度 3.1定义 3.2常见空间复杂度计算举例 1.算法效率 算法的效率常用算法复杂度来衡量&#xff0c;算法复杂度描述了算法在输入数据规模变化时&#xff0c;其运行时间和空间…

rocketmq管理工具rocketmq-console安装

rocketmq-console是一个图形化管理控制台&#xff0c;提供Broker集群状态查看&#xff0c;Topic管理&#xff0c;Producer、Consumer状态展示&#xff0c;消息查询等常用功能&#xff0c;这个功能在安装好RocketMQ后需要额外单独安装、运行。 中文文档地址&#xff1a;https:/…

科技团队治理能力成长路线图

点击&#x1f446;蓝字 关注我们 本文观点&#xff5c;吴穹 主笔&#xff5c;AI小助手 温馨提示&#xff1a;干货长文&#xff0c;建议收藏阅读喔&#xff5e; 引言 2024年3月20日&#xff0c;吴穹博士于上海交通大学上海高级金融学院同一众信托行业金融科技管理者进行了《金融…

基于opencv的SVM算法的车牌识别系统设计与实现

基于opencv的SVM算法的车牌识别系统设计与实现 车牌识别技术是智能交通系统中的一项关键技术&#xff0c;它能够自动识别车辆的车牌号码。本文将详细介绍如何使用Python编程语言结合OpenCV库和SVM算法来实现车牌识别系统。 系统架构 车牌识别系统主要包括以下几个模块&…

前端学习<四>JavaScript基础——01-编程语言和JavaScript简介

计算机语言 概念 计算机语言&#xff1a;人与计算机之间通信的语言。它是人与计算机之间传递信息的媒介&#xff0c;它通过特定的语法规则和语义约定&#xff0c;将人类可理解的指令转化为计算机可以执行的机器指令。 计算机程序&#xff1a;就是计算机所执行的一系列的指令…

docker 部署项目

编写Dockerfile #FROM&#xff1a;基于java:8镜像构建 FROM openjdk:8 #EXPOSE&#xff1a;监听8080端口&#xff0c;暴露容器的8080端口&#xff0c;该端口余项目端口需要一致 EXPOSE 8080 #ARG&#xff1a;引用plugin中配置的 JAR_FILE 文件 ARG JAR_FILE #ADD&#xff1a;将…

OpenHarmony实战:轻量级系统之安全子系统移植

安全子系统提供网络设备连接、认证鉴权等功能&#xff0c;依赖mbedtls实现硬件随机数以及联网功能。 由于每个厂商芯片硬件与实现硬件随机数的方式不同&#xff0c;需要适配硬件随机数接口。 移植指导 OpenHarmony提供了mbedtls的开源三方库&#xff0c;路径为“//third_par…

人人都离不开的算法:AI 时代的生存指南

文章目录 一、算法在生活中的“无处不在”二、算法在工作学习中的“智慧助力”三、算法在社会发展中的“驱动力量”四、算法带来的“双刃剑”效应五、应对算法挑战的策略《人人都离不开的算法——图解算法应用》编辑推荐1、通俗易懂2、技术科普3、贴近时代、贴近生活4、启发思考…

[C++]使用OpenCV去除面积较小的连通域

这是后期补充的部分&#xff0c;和前期的代码不太一样 效果图 源代码 //测试 void CCutImageVS2013Dlg::OnBnClickedTestButton1() {vector<vector<Point> > contours; //轮廓数组vector<Point2d> centers; //轮廓质心坐标 vector<vector<Point&…

Android的图片加载框架

Android的图片加载框架 为什么要使用图片加载框架&#xff1f;图片加载框架1. Universal Image Loader [https://github.com/nostra13/Android-Universal-Image-Loader](https://github.com/nostra13/Android-Universal-Image-Loader)2. Glide [https://muyangmin.github.io/gl…

文献速递:深度学习胰腺癌诊断--深度学习算法用于从疾病轨迹预测胰腺癌风险

文献速递&#xff1a;深度学习胰腺癌诊断--深度学习算法用于从疾病轨迹预测胰腺癌风险 麦田医学 美好事物中转站 2024-04-02 14:36 Title 题目 A deep learning algorithm to predict risk of pancreatic cancer from disease trajectories 深度学习算法用于从疾病轨迹预测…

vue中使用图片url直接下载图片

vue中使用图片url直接下载图片 // 下载图片downloadByBlob(url, name) {let image new Image()image.setAttribute(crossOrigin, anonymous)image.src urlimage.onload () > {let canvas document.createElement(canvas)canvas.width image.widthcanvas.height image…

pymc,一个灵活的的 Python 概率编程库!

目录 前言 安装与配置 概率模型 贝叶斯推断 概率分布 蒙特卡罗采样 贝叶斯网络 实例分析 PyMC库的应用场景 1. 概率建模 2. 时间序列分析 3. 模式识别 总结 前言 大家好&#xff0c;今天为大家分享一个超强的 Python 库 - pymc Github地址&#xff1a;https://gith…

2024最新软件测试【测试理论+ 性能测试】面试题(内附答案)

一、测试理论 3.1 你们原来项目的测试流程是怎么样的? 我们的测试流程主要有三个阶段&#xff1a;需求了解分析、测试准备、测试执行。 1、需求了解分析阶段 我们的 SE 会把需求文档给我们自己先去了解一到两天这样&#xff0c;之后我们会有一个需求澄清会议&#xff0c; …

JavaScript 对象管家 Proxy

JavaScript 在 ES6 中&#xff0c;引入了一个新的对象类型 Proxy&#xff0c;它可以用来代理另一个对象&#xff0c;并可以在代理过程中拦截、覆盖和定制对象的操作。Proxy 对象封装另一个对象并充当中间人&#xff0c;其提供了一个捕捉器函数&#xff0c;可以在代理对象上拦截…

3.恒定乘积自动做市商算法及代码

中心化交易所的安全风险 在中心化交易所中注册账户时&#xff0c;是由交易所生成一个地址&#xff0c;用户可以向地址充币&#xff0c;充到地址之后交易所就会根据用户充币的数量显示在管理界面中。但是充币的地址是掌管在交易所之中的&#xff0c;资产的控制权还是在交易所。…

用于自动驾驶,无人驾驶领域的IMU六轴陀螺仪传感器:M-G370

用于自动驾驶,无人驾驶的IMU惯导模块六轴陀螺仪传感器:M-G370。自2020年&#xff0c;自动驾驶,无人驾驶已经迎来新突破&#xff0c;自动驾驶汽车作为道路交通体系的一员&#xff0c;要能做到的就是先判断周边是否有障碍物&#xff0c;自身的行驶是否会对其他交通参与成员产生危…