LeetCode 658.找到K个最接近的元素

给定一个 排序好 的数组 arr ,两个整数 k 和 x ,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足:

|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b

示例 1:

输入:arr = [1,2,3,4,5], k = 4, x = 3
输出:[1,2,3,4]
示例 2:

输入:arr = [1,1,2,3,4,5], k = 4, x = -1
输出:[1,1,2,3]

提示:

1 <= k <= arr.length
1 <= arr.length <= 104^44
arr 按 升序 排列
-104^44 <= arr[i], x <= 104^44

相向双指针,我们需要从arr里删去arr.size()-k个元素:

class Solution {
public:vector<int> findClosestElements(vector<int>& arr, int k, int x) {int left = 0;int right = arr.size() - 1;int deleteNum = 0;while (left < right) {if (deleteNum == arr.size() - k) {break;}if (abs(arr[left] - x) > abs(arr[right] - x)) {++left;} else {--right;}++deleteNum;}return vector<int>(arr.begin() + left, arr.begin() + right + 1);}
};

如果arr的长度为n,则此算法时间复杂度为O(n - k),空间复杂度为O(1)。

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

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

相关文章

制作一款打飞机游戏83:炸弹机制

游戏中的炸弹系统&#xff0c;包括以下核心功能&#xff1a;炸弹爆炸效果与动画实现炸弹伤害范围判定机制子弹转化为能量道具的系统炸弹使用时的无敌帧处理各种边界情况的修复与优化技术实现细节1. 炸弹基础系统‌炸弹动画状态机‌&#xff1a; 我们采用三阶段状态机控制炸弹效…

Linux CentOS 虚拟机升级内核至4.x以上版本

1、安装组件 yum install -y wget && yum install -y net-tools yum groupinstall “Development Tools” yum install ncurses-devel bc openssl-devel elfutils-libelf-devel yum install -y ncurses-devel yum install -y elfutils-libelf-devel yum install -y ope…

QT跨平台应用程序开发框架(11)—— Qt系统相关

目录 一&#xff0c;事件 1.1 关于事件 1.2 处理事件 1.3 处理鼠标事件 1.3.1 点击事件 1.3.2 释放事件 1.3.3 双击事件 1.3.4 滚轮事件 1.3.5 注意事项 1.4 处理键盘事件 1.5 定时器事件 1.6 窗口移动和大小改变事件 二&#xff0c;文件操作 2.1 文件操作概述 2.2 QFile 介绍…

sqli-labs通关笔记-第11关 POST字符型注入(单引号闭合 手工注入+脚本注入两种方法)

目录 一、字符型注入 二、limit函数 三、GET方法与POST方法 四、源码分析 1、代码审计 2、SQL注入安全分析 五、渗透实战 1、进入靶场 2、注入点分析 &#xff08;1&#xff09;SQL语句 &#xff08;2&#xff09;万能密码登录 3、手工注入 &#xff08;1&#xf…

网络安全基础作业三

回顾web前端的代码<!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>用户登录</title><st…

基于单片机的温湿度报警系统设计与实现

摘 要 本项研究对温湿度警报系统的需求进行了详尽分析&#xff0c;并成功研制出一套以单片机为技术核心的温湿度警报系统。该系统由硬件搭建和软件编程两大模块构成。在硬件搭建方面&#xff0c;系统整合了STM32主控芯片、DS18B20温度传感器、湿敏电阻、按键组件、OLED显示屏、…

(八)复习(拆分微服务)

文章目录项目地址一、Ticketing模块拆分1.1 创建web api1. 添加引用2. 添加需要的包和配置3. program.cs4. docker-compose修改项目地址 教程作者&#xff1a;教程地址&#xff1a; 代码仓库地址&#xff1a; 所用到的框架和插件&#xff1a; dbt airflow一、Ticketing模块拆…

DearMom以“新生儿安全系统”重塑婴儿车价值,揽获CBME双项大奖

7月16日&#xff0c;在刚刚开幕的2025 CBME中国孕婴童展上&#xff0c;备受瞩目的CBME中国孕婴童产业奖正式揭晓。深耕婴儿车品类的专业品牌DearMom&#xff0c;凭借其卓越的创新实力与对新生儿安全出行的深刻洞察&#xff0c;一举摘得重量级奖项——“杰出品牌创新奖”。同时&…

瀚高数据库开启Oracle兼容模块

文章目录环境症状问题原因解决方案环境 系统平台&#xff1a;Linux x86-64 Red Hat Enterprise Linux 7 版本&#xff1a;4.5 症状 不能使用Oracle兼容&#xff1b; 问题原因 在瀚高数据库V45中oracle兼容模块需要单独开启默认是关闭状态。 解决方案 使用sysdba执行修改…

final修饰符不可变的底层

final修饰符的底层原理在 Java 中&#xff0c;final 修饰符的底层实现涉及 编译器优化 和 JVM 字节码层面的约束其核心目标是保证被修饰元素的【不可变性】或 【不可重写 / 继承性】一、final 修饰类&#xff1a;禁止继承的底层约束当一个类被 final 修饰时&#xff0c;例如 St…

如何排查服务器 CPU 飙高

服务器 CPU 飙高&#xff08;CPU 使用率持续超过 80% 甚至接近 100%&#xff09;是典型的性能瓶颈问题&#xff0c;可能由应用逻辑缺陷、资源竞争、外部压力或硬件/系统异常引起。以下是系统化的排查步骤&#xff0c;覆盖从现象确认到根因定位的全流程。​一、确认 CPU 飙高的现…

【DataWhale】快乐学习大模型 | 202507,Task05笔记

前言 今天是Transformer的编码实战阶段&#xff0c;照着示例代码执行一遍吧 embedding self.tok_embeddings nn.Embedding(args.vocab_size, args.dim)把token向量转为embedding矩阵&#xff08;一个token一个embedding向量&#xff09; 位置编码 为了解决“我喜欢你”和…

用ffmpeg 进行视频的拼接

author: hjjdebug date: 2025年 07月 22日 星期二 17:06:02 CST descrip: 用ffmpeg 进行视频的拼接 文章目录1. 指定协议为concat 方式.1.1 协议为concat 模式,会调用 concat_open 函数1.2 当读数据时,会调用concat_read2. 指定file_format 为 concat 方式2.1 调用concat_read_…

HTTP与HTTPS技术细节及TLS密钥交换与证书校验全流程

HTTP与HTTPS技术细节及TLS密钥交换与证书校验全流程 引言 文档目的与范围 核心技术栈概述 本文档的核心技术栈围绕传输层安全协议&#xff08;TLS&#xff09;展开。TLS协议作为安全套接字层&#xff08;SSL&#xff09;的后继标准&#xff0c;是现代网络安全通信的基础&am…

广播分发中心-广播注册流程

广播是怎么注册的呢&#xff1f;阶段组件/数据结构作用描述存储位置/关联关系App进程阶段BroadcastReceiver开发者自定义的广播接收器&#xff0c;实现onReceive方法处理事件。App进程&#xff08;Activity/Service等组件内&#xff09;ReceiverDispatcher将BroadcastReceiver封…

OpenCV计算机视觉实战(16)——图像分割技术

OpenCV计算机视觉实战&#xff08;16&#xff09;——图像分割技术0. 前言1. 分水岭算法1.1 应用场景1.2 实现过程2. GrabCut 交互式分割2.1 应用场景2.2 实现过程3. FloodFill3.1 应用场景3.2 实现过程小结系列链接0. 前言 图像分割是计算机视觉中将像素划分为具有特定语义或…

Coturn打洞服务器

* 概念理解&#xff1a;1. SDP协议&#xff1a;会话描述协议&#xff0c;视频通话的双方通过交换SDP信息进行媒体协商&#xff0c;从而选择使用某一相同的媒体协议进行通信&#xff1b;TLS协议&#xff1a;基于TCP的安全层传输协议DTLS协议&#xff1a;基于UDP的安全层传输协议…

python flusk 监控

# 创建虚拟环境目录 python3 -m venv /sda1/xunjian/venv # 激活虚拟环境 source /sda1/xunjian/venv/bin/activate # 激活后终端会显示 (venv)创建虚拟环境&#xff08;在当前目录&#xff09;&#xff1a;bashpython3 -m venv venv激活虚拟环境&#xff1a;bashsource venv/b…

VUE2 项目学习笔记 ? 语法 v-if/v-show

?语法页面渲染的时候&#xff0c;需要服务器传过来的对象中的一个属性&#xff0c;然后根据这个属性用v-for渲染标签&#xff0c;这里写的v-for".... in dataList.goodsList"但是当解析到这行语法的时候&#xff0c;dataList还没返回&#xff0c;因此控制台会报错找…

使用qemu命令启动虚拟机

1. 安装相关软件 yum install qemu edk2* libvirt -y 启动libvirt服务 systemctl start libvirtd systemctl status libvirtd2. 创建虚拟机 2.1. qemu启动命令示例 /usr/bin/qemu-system-loongarch64 \-machine virt,accelkvm \-nodefaults \-m 2048 \-smp 2,maxcpus4,co…