用C++编写一个程序，找出数组中所有元素对之间第k小的差值

WBOY

发布时间：2023-09-05 17:25:06

1246人浏览过

来源于tutorialspoint

转载

用c++编写一个程序，找出数组中所有元素对之间第k小的差值

假设我们有一个包含多个整数的列表。我们必须找出数组中每对值之间的差异，并找出第 k 个最小的差异数。索引从 0 开始，值 k 作为输入提供给我们。

因此，如果输入类似于numbers = {2, 6, 4, 8}, k = 2，那么输出将为 2。

两对之间的差异为 -

(2, 6) = 4

立即学习“C++免费学习笔记（深入）”；

(2, 4) = 2

数说Social Research

社媒领域的AI Agent，全能营销智能助手

下载

(2, 8) = 6

(6, 4) = 2

(6, 8) = 2

(4, 8) = 4

如果我们对这些值进行排序，它会变成 2, 2, 2, 4, 4, 6。第二个最小值是 2。（索引从 0)。

为了解决这个问题，我们将按照以下步骤操作 -

将 k 增加 1
对数组输入进行排序
le := 0
ri := 输入的最后一个元素 - 输入的第一项
while le
mid := (le + ri) / 2
tmp := 0
lp := 0
用于初始化 i := 1 ，当 i
while input[i] - input[lp] > mid，执行 −
- lp := lp + 1
tmp := tmp + i - lp

如果tmp >= k，则 -

ri := mid

否则

le := mid + 1

返回le

示例

令我们看下面的实现来更好地理解 -

#include

using namespace std;

int solve(vector& input, int k) {
k++;
sort(input.begin(), input.end());
int le = 0;
int ri = input.back() - input[0];
while (le < ri) {
int mid = (le + ri) / 2;
long long tmp = 0;
int lp = 0;
for (int i = 1; i < input.size(); i++) {
while (input[i] - input[lp] > mid) lp++;
tmp += i - lp;
}
if (tmp >= k)
ri = mid;
else
le = mid + 1;
}
return le;
}
int main() {
vector numbers = {2, 6, 4, 8};
cout<< solve(numbers, 2) <输入
vector numbers = {2, 6, 4, 8};
cout<< solve(numbers, 2) <输出
2

C++ vector reserve作用 C++ 预分配内存减少拷贝次数【效率】

C++ 怎么遍历vector删除元素 C++迭代器失效问题的正确解法【避坑】

C++ map emplace用法 C++ 原地构造键值对提升效率【优化】

C++ remove_if怎么用 C++ 结合lambda删除容器元素【常用】

C++ static变量初始化时机 C++静态生命周期深度解析【基础】

c++速学教程(入门到精通)

c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

while input

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：寻找抛物线的顶点、焦点和准线的C/C++程序下一篇：在C语言中，条件编译是什么意思？

作者最新文章

夸克浏览器AI搜索最新版教学_探索夸克AI搜索的隐藏功能

2025-10-24 20:48

夸克浏览器怎么用AI搜索_夸克AI搜索正确提问方式教学

2025-10-25 23:12

微信朋友圈怎么设置定时发布微信朋友圈定时发送图文教程

2026-01-02 09:14

微信朋友圈怎么定时发送微信朋友圈定时发布设置方法【教程】

2026-01-06 09:59

苹果手机怎么定时发朋友圈 iPhone微信朋友圈自动发布方法【步骤】

2026-01-08 11:11

微信朋友圈能定时发送吗微信朋友圈定时发送功能开启方法

2026-01-09 08:15

微信朋友圈草稿箱怎么用微信朋友圈定时发送隐藏技巧

2026-01-10 08:41

微信朋友圈定时发送是真的吗微信朋友圈预约发布实现方法

2026-01-15 10:19

微信定时发朋友圈怎么弄微信朋友圈自动推送设置流程

2026-01-21 04:27

微信如何定时发朋友圈微信朋友圈自动定时发送设置步骤【汇总】

2026-01-23 10:22

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI 编程开发 AI 聊天问答

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI 编程开发 AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI 编程开发 Agent智能体

腾讯元宝

腾讯混元平台推出的AI助手

文档处理 AI 聊天问答

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI 编程开发 AI 文本写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

AI 文本写作中文写作

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI 编程开发 AI 文本写作

智谱清言 - 免费全能的AI助手

AI 编程开发 Agent智能体

相关专题

while的用法

while的用法是“while 条件: 代码块”，条件是一个表达式，当条件为真时，执行代码块，然后再次判断条件是否为真，如果为真则继续执行代码块，直到条件为假为止。本专题为大家提供while相关的文章、下载、课程内容，供大家免费下载体验。

2023.09.25

点击input框没有光标怎么办

点击input框没有光标的解决办法：1、确认输入框焦点；2、清除浏览器缓存；3、更新浏览器；4、使用JavaScript；5、检查硬件设备；6、检查输入框属性；7、调试JavaScript代码；8、检查页面其他元素；9、考虑浏览器兼容性。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

185

2023.11.24

拼多多赚钱的5种方法拼多多赚钱的5种方法

在拼多多上赚钱主要可以通过无货源模式一件代发、精细化运营特色店铺、参与官方高流量活动、利用拼团机制社交裂变，以及成为多多进宝推广员这5种方法实现。核心策略在于通过低成本、高效率的供应链管理与营销，利用平台社交电商红利实现盈利。

2026.01.26

edge浏览器怎样设置主页 edge浏览器自定义设置教程

在Edge浏览器中设置主页，请依次点击右上角“...”图标 > 设置 > 开始、主页和新建标签页。在“Microsoft Edge 启动时”选择“打开以下页面”，点击“添加新页面”并输入网址。若要使用主页按钮，需在“外观”设置中开启“显示主页按钮”并设定网址。

2026.01.26

苹果官方查询网站苹果手机正品激活查询入口

苹果官方查询网站主要通过 checkcoverage.apple.com/cn/zh/ 进行，可用于查询序列号（SN）对应的保修状态、激活日期及技术支持服务。此外，查找丢失设备请使用 iCloud.com/find，购买信息与物流可访问 Apple (中国大陆) 订单状态页面。

2026.01.26

npd人格什么意思 npd人格有什么特征

NPD（Narcissistic Personality Disorder）即自恋型人格障碍，是一种心理健康问题，特点是极度夸大自我重要性、需要过度赞美与关注，同时极度缺乏共情能力，背后常掩藏着低自尊和不安全感，影响人际关系、工作和生活，通常在青少年时期开始显现，需由专业人士诊断。

2026.01.26

windows安全中心怎么关闭 windows安全中心怎么执行操作

关闭Windows安全中心（Windows Defender）可通过系统设置暂时关闭，或使用组策略/注册表永久关闭。最简单的方法是：进入设置 > 隐私和安全性 > Windows安全中心 > 病毒和威胁防护 > 管理设置，将实时保护等选项关闭。

2026.01.26

2026年春运抢票攻略大全春运抢票攻略教你三招手【技巧】

铁路12306提供起售时间查询、起售提醒、购票预填、候补购票及误购限时免费退票五项服务，并强调官方渠道唯一性与信息安全。

2026.01.26

个人所得税税率表2026 个人所得税率最新税率表

以工资薪金所得为例，应纳税额 = 应纳税所得额 × 税率 - 速算扣除数。应纳税所得额 = 月度收入 - 5000 元 - 专项扣除 - 专项附加扣除 - 依法确定的其他扣除。假设某员工月工资 10000 元，专项扣除 1000 元，专项附加扣除 2000 元，当月应纳税所得额为 10000 - 5000 - 1000 - 2000 = 2000 元，对应税率为 3%，速算扣除数为 0，则当月应纳税额为 2000×3% = 60 元。

2026.01.26

热门下载

网站特效

网站源码

网站素材

前端模板