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

排序题目:最小绝对差

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:最小绝对差

出处:1200. 最小绝对差

难度

2 级

题目描述

要求

给定整数数组 arr \texttt{arr} arr,其中每个元素都不相同,找到所有具有最小绝对差的元素对。

按升序的顺序返回元素对列表,每个元素对 [a, b] \texttt{[a, b]} [a, b] 满足:

  • a, b \texttt{a, b} a, b 是数组 arr \texttt{arr} arr 中的元素。
  • a < b \texttt{a} < \texttt{b} a<b
  • b − a \texttt{b} - \texttt{a} ba 等于数组 arr \texttt{arr} arr 中的任意两个元素的最小绝对差。

示例

示例 1:

输入: arr = [4,2,1,3] \texttt{arr = [4,2,1,3]} arr = [4,2,1,3]
输出: [[1,2],[2,3],[3,4]] \texttt{[[1,2],[2,3],[3,4]]} [[1,2],[2,3],[3,4]]
解释:最小绝对差是 1 \texttt{1} 1。将所有绝对差等于 1 \texttt{1} 1 的元素对按升序的顺序加入列表并返回。

示例 2:

输入: arr = [1,3,6,10,15] \texttt{arr = [1,3,6,10,15]} arr = [1,3,6,10,15]
输出: [[1,3]] \texttt{[[1,3]]} [[1,3]]

示例 3:

输入: arr = [3,8,-10,23,19,-4,-14,27] \texttt{arr = [3,8,-10,23,19,-4,-14,27]} arr = [3,8,-10,23,19,-4,-14,27]
输出: [[-14,-10],[19,23],[23,27]] \texttt{[[-14,-10],[19,23],[23,27]]} [[-14,-10],[19,23],[23,27]]

数据范围

  • 2 ≤ arr.length ≤ 10 5 \texttt{2} \le \texttt{arr.length} \le \texttt{10}^\texttt{5} 2arr.length105
  • -10 6 ≤ arr[i] ≤ 10 6 \texttt{-10}^\texttt{6} \le \texttt{arr[i]} \le \texttt{10}^\texttt{6} -106arr[i]106

解法

思路和算法

当数组有序时,每个元素的相邻元素是数组中与该元素最接近的元素,因此最小绝对差一定是排序后的数组中的两个相邻元素之差。

首先将数组排序,然后遍历排序后的数组,计算每一对相邻元素的绝对差,即可得到最小绝对差。

得到最小绝对差之后,再次遍历排序后的数组,计算每一对相邻元素的绝对差,当相邻元素的绝对差等于最小绝对差时,将这一对相邻元素添加到结果列表中,遍历结束之后即可得到所有具有最小绝对差的元素对。

由于是遍历排序后的数组寻找具有最小绝对差的元素对,因此遍历元素对的顺序是递增顺序,可以确保结果列表中的元素对按升序的顺序排列。

代码

class Solution {public List<List<Integer>> minimumAbsDifference(int[] arr) {Arrays.sort(arr);int minDiff = arr[1] - arr[0];int length = arr.length;for (int i = 2; i < length; i++) {minDiff = Math.min(minDiff, arr[i] - arr[i - 1]);}List<List<Integer>> pairs = new ArrayList<List<Integer>>();for (int i = 1; i < length; i++) {if (arr[i] - arr[i - 1] == minDiff) {List<Integer> pair = new ArrayList<Integer>();pair.add(arr[i - 1]);pair.add(arr[i]);pairs.add(pair);}}return pairs;}
}

复杂度分析

  • 时间复杂度: O ( n log ⁡ n ) O(n \log n) O(nlogn),其中 n n n 是数组 arr \textit{arr} arr 的长度。排序需要 O ( n log ⁡ n ) O(n \log n) O(nlogn) 的时间,每次遍历数组需要 O ( n ) O(n) O(n) 的时间,总时间复杂度是 O ( n log ⁡ n ) O(n \log n) O(nlogn)

  • 空间复杂度: O ( log ⁡ n ) O(\log n) O(logn),其中 n n n 是数组 arr \textit{arr} arr 的长度。排序需要 O ( log ⁡ n ) O(\log n) O(logn) 的递归调用栈空间。注意返回值不计入空间复杂度。

相关文章:

排序题目:最小绝对差

文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;最小绝对差 出处&#xff1a;1200. 最小绝对差 难度 2 级 题目描述 要求 给定整数数组 arr \texttt{arr} arr&#xff0c;其中每个元素都不相同&…...

沃飞携AE200真机亮相澳门,全方位赋能城市低空出行

5月22日-25日&#xff0c;第四届BEYOND国际科技创新博览会&#xff08;BEYOND Expo 2024&#xff09;在澳门盛大举行。吉利沃飞长空携旗下全自研产品AE200真机亮相&#xff0c;吸引了现场众多领导嘉宾以及媒体、观众的关注。 作为亚洲顶尖的年度科技盛会&#xff0c;本届BEYOND…...

判断当前系统是linux、windows还是MacOS (python)

在很多情况下&#xff0c;需要在python中获取当前系统的类型&#xff0c;用于判断是unix/windows/mac或者java虚拟机等&#xff0c;python中提供了os.name&#xff0c; sys.platform&#xff0c; platform.system等方式 sys sys.platform会返回当前系统平台的标识符&#xff…...

Minikube部署单节点Kubernetes

1.1 Minikube部署单节点K8s Minikube是由Kubernetes社区维护的单机版的Kubernetes集群&#xff0c;支持macOS, Linux, andWindows等多种操作系统平台&#xff0c;使用最新的官方stable版本&#xff0c;并支持Kubernetes的大部分功能&#xff0c;从基础的容器编排管理&#xff0…...

leetcode-顺时针旋转矩阵-111

题目要求 思路 1.假设现在有一个矩阵 123 456 789 2.我们可以根据19这个对角线将数据进行交换&#xff0c;得到矩阵 147 258 369 3.然后将矩阵每一行的数据再翻转&#xff0c;得到矩阵 741 852 963 代码实现 class Solution { public:vector<vector<int> > rot…...

解决GoLand无法Debug

goland 调试的的时候提示如下错误 WARNING: undefined behavior - version of Delve is too old for Go version 1.22.3 (maximum supported v 其实个原因是因为正在使用的Delve调试器版本太旧&#xff0c;无法兼容当前的Go语言版本1.22.3。Delve是Go语言的一个调试工具&#…...

云原生周刊:K8s 上的 gRPC 名称解析和负载平衡

开源项目推荐 Kraken Kraken 是一个基于 P2P 的 Docker 注册表&#xff0c;专注于可扩展性和可用性。它专为混合云环境中的 Docker 镜像管理、复制和分发而设计。借助可插拔的后端支持&#xff0c;Kraken 可以轻松集成到现有的 Docker 注册表设置中作为分发层。 E2E Framewo…...

从0开始回顾ElasticSearch

1 elasticsearch概述 1.1 elasticsearch简介 官网: https://www.elastic.co/ ElasticSearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎&#xff0c;基于RESTful web接口。Elasticsearch是用Java开发的&#xff0c;并作为Apache许可条款下的…...

小阿轩yx-Shell编程之条件语句

小阿轩yx-Shell编程之条件语句 条件测试操作 Shell 环境根据命令执行后的返回状态值&#xff08;$?&#xff09;来判断是否执行成功 返回值 为 0 时&#xff1a;表示成功否则&#xff08;非 0 值&#xff09;表示失败或异常 测试工具 test 命令&#xff0c;对特定条件进行…...

MyBatis-Plus 从入门到精通

MyBatis-Plus 从入门到精通 前言快速入门创建一个SpringBoot项目导入依赖配置数据库创建一个实体类创建一个mapper接口在SpringBoot启动类上配置mapper接口的扫描路径在数据库中创建表编写一个SpringBoot测试类 核心功能注解CRUD接口Mapper CRUD接口Service CRUD 接口条件构造器…...

爬虫利器Frida RPC入门——夜神模拟器环境篇

Frida是一款轻量级HOOK框架&#xff0c;可用于多平台上&#xff0c;例如android、windows、ios等。 frida分为两部分&#xff0c;服务端运行在目标机上&#xff0c;通过注入进程的方式来实现劫持应用函数&#xff0c;另一部分运行在系统机器上。frida上层接口支持js、python、…...

猫狗分类识别模型建立①数据标记

一、labelImg库说明 LabelImg是一款非常流行的图像标注工具&#xff0c;广泛用于机器学习和计算机视觉领域。以下是关于LabelImg的详细介绍&#xff1a; 主要功能和特点 1.图像标注 允许用户在图像中标注物体&#xff0c;选择特定区域&#xff0c;并为这些区域添加标签或类…...

FME学习之旅---day28

我们付出一些成本&#xff0c;时间的或者其他&#xff0c;最终总能收获一些什么。 教程&#xff1a;CSV 入门...

vue3项目中字典和全局方法的创建与使用

在src下新建dict.ts/js,写入下面代码 import { App, Plugin } from vue;interface Dict {auditgrouptypeList: { label: string; value: string }[];auditstateList: { label: string; value: string }[];accountchangeList: { label: string; value: number }[]; }const Dict…...

51-54 Sora能制作动作大片还需要一段时间 | DrivingGaussian:周围动态自动驾驶场景的复合高斯飞溅

24年3月&#xff0c;北大、谷歌和加州大学共同发布了DrivingGaussian: Composite Gaussian Splatting for Surrounding Dynamic Autonomous Driving Scenes。视图合成和可控模拟可以生成自动驾驶的极端场景Corner Case&#xff0c;这些安全关键情况有助于以更低成本验证和增强自…...

数据挖掘实战-基于余弦相似度的印度美食推荐系统

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

深入探索DreamFusion:文本到3D生成的革命性技术

深入探索DreamFusion&#xff1a;文本到3D生成的革命性技术 引言&#xff1a; 在人工智能和计算机视觉领域&#xff0c;DreamFusion无疑是一个引人注目的新星。这项技术&#xff0c;基于Google提出的深度学习模型&#xff0c;将自然语言与三维内容生成紧密结合&#xff0c;开…...

JSP期末要点复习

一、JSP工作原理 1.客户端请求JSP页面&#xff1a;用户通过浏览器发送一个请求到服务器&#xff0c;请求一个特定的JSP页面。这个请求被服务器上的Web容器&#xff08;如Apache Tomcat&#xff09;接收。 2.JSP转换为Servlet&#xff1a;当JSP页面第一次被请求时&#xff0…...

AJAX(JavaScript版本)

目录 一.AJAX简介 二.XMLHttpRequests对象 2.1XMLHttpRequests对象简介 2.2创建XMLHttpRequests对象 2.3定义回调函数 2.4发送请求 2.5XMLHttpRequests对象方法介绍 2.6XMLHttpRequests对象属性 三.向服务器发送请求 3.1发送请求 3.2使用GET还是POST 3.3使用GET来发…...

框架学习之SpringMVC学习笔记(一)

一、SpringMVC简介 1-介绍 Spring Web MVC是基于Servlet API构建的原始Web框架&#xff0c;从一开始就包含在Spring Framework中。正式名称“Spring Web MVC”来自其源模块的名称&#xff08; spring-webmvc &#xff09;&#xff0c;但它通常被称为“Spring MVC”。 在控制层…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...