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

力扣164最大间距

1.前言

        因为昨天写了一个基数排序,今天我来写一道用基数排序实现的题解,希望可以帮助你理解基数排序。

这个题本身不难,就是线性时间和线性额外空间(O(n))的算法,有点难实现

 基数排序的时间复杂度是O(d*(n+radix)),其中d是最大值的位数,n是数组长度,radix是基数(10)然后化简就是 O(n) 

2.思路分析

  1. 首先,找到待排序数组中的最大值,确定最大值的位数。假设最大值是max,位数是d。

  2. 创建10个桶(0-9),每个桶用来存放对应位数上的数字。

  3. 从低位(个位)开始,根据当前位数的值将待排序数组中的数字放入对应的桶中。

  4. 将桶中的数字按照顺序取出,覆盖原数组,然后进入下一位数的排序。

  5. 重复步骤3和步骤4,直到排完最高位(即 d 位)。

  6. 最后,遍历排序后的数组,计算相邻数字之间的差值,找到最大的差值,即为最大间距。

3.代码实现 

这里我获取最大值最小值使用了stream流,下面我来介绍一下

int maxVal = Arrays.stream(arr).max().getAsInt();  获取最大值

//Arrays.stream(arr) 将数组转换为一个流。
//max() 方法找到流中的最大值,返回一个 OptionalInt 对象。
//getAsInt() 方法从 OptionalInt 对象中获取最大值作为 int 类型的值。如果最大值不存在(即数组为空),则会抛出 NoSuchElementException 异常。

/*
* 基数排序实现  求相邻元素的差值(最大间距)
*
* */import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class sortHomework3 {public static int maximumGap(int[] nums) {radixSort(nums);int r = 0;for (int i = 1; i < nums.length; i++) {r = Math.max(r,nums[i] - nums[i - 1]);}return r;}public static void radixSort(int[] arr) {if (arr == null || arr.length == 0){return;}int max = Arrays.stream(arr).max().getAsInt();//获得最大值,确定最高位数int min = Arrays.stream(arr).min().getAsInt();//获得最小值int digit = 1; // 从最低位开始排序int base = 10; // 基数为10,即十进制(是个桶)// 转换负数为正数if (min < 0) {max -= min;for (int i = 0; i < arr.length; i++) {arr[i] -= min;}}while(max / digit > 0){countingSort(arr, base, digit);digit *= base;//处理更高位数}//排序完毕后// 将转换后的正数转换回负数if (min < 0) {for (int i = 0; i < arr.length; i++) {arr[i] += min;}}}private static void countingSort(int[] arr, int base, int digit) {// 定义桶的大小 (里面的泛型<表示动态数组>)为10个桶List<List<Integer>> buckets = new ArrayList<>(10);for (int i = 0; i < 10; i++) {buckets.add(new ArrayList<>()); // 创建空的桶(不创建空桶默认里面存的都是null不是桶)}for (int i : arr) {int index = i / digit % base;//获得位数buckets.get(index).add(i);//添加到集合中}int k = 0;//将元素在插入arr中for (int i = 0; i < buckets.size(); i++) {if (buckets.get(i).isEmpty()){continue;}//把各个桶中的元素存储到数组中for (int j = 0; j < buckets.get(i).size(); j++) {arr[k++] = buckets.get(i).get(j);}//取出来一个桶,咱就删除一个桶buckets.get(i).clear();}}public static void main(String[] args) {int[] arr = {5, 2, 8000, 3, 1};int[] expected = {1, 2, 3, 5, 8};System.out.println(Arrays.toString(arr));maximumGap(arr);System.out.println(Arrays.toString(arr));}
}

相关文章:

力扣164最大间距

1.前言 因为昨天写了一个基数排序&#xff0c;今天我来写一道用基数排序实现的题解&#xff0c;希望可以帮助你理解基数排序。 这个题本身不难&#xff0c;就是线性时间和线性额外空间(O(n))的算法&#xff0c;有点难实现 基数排序的时间复杂度是O(d*(nradix))&#xff0c;其中…...

聚观早报 | “百度世界2023”即将举办;2024款岚图梦想家上市

【聚观365】10月13日消息 “百度世界2023”即将举办 2024款岚图梦想家上市 腾势D9用户超10万 华为发布新一代GigaGreen Radio OpenAI拟进行重大更新 “百度世界2023”即将举办 “百度世界2023”将于10月17日在北京首钢园举办。届时&#xff0c;百度创始人、董事长兼首席执…...

Windows 应用程序监控重启

执行思路 1.定时关闭可执行程序&#xff0c;2.再通过定时监控启动可执行程序 定时启动关闭程序.bat echo off cd "D:\xxxx\" :: 可执行程序目录 Start "" /b xxxx.exe :: 可执行程序 timeout /T 600 /nobreak >nul :: 600秒 taskkill /IM xxxx.exe /…...

springboot 通过url下载文件并上传到OSS

DEMO流程 传入一个需要下载并上传的url地址下载文件上传文件并返回OSS的url地址 springboot pom文件依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w…...

docker创建elasticsearch、elasticsearch-head部署及简单操作

elasticsearch部署 1 拉取elasticsearch镜像 docker pull elasticsearch:7.7.0 2 创建文件映射路径 mkdir /mydata/elasticsearch/data mkdir /mydata/elasticsearch/plugins mkdir /mydata/elasticsearch/config 3 文件夹授权 chmod 777 /mydata/elastic…...

竞赛选题 深度学习+python+opencv实现动物识别 - 图像识别

文章目录 0 前言1 课题背景2 实现效果3 卷积神经网络3.1卷积层3.2 池化层3.3 激活函数&#xff1a;3.4 全连接层3.5 使用tensorflow中keras模块实现卷积神经网络 4 inception_v3网络5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; *…...

Codeforces Round 903 (Div. 3)ABCDE

Codeforces Round 903 (Div. 3)ABCDE 目录 A. Dont Try to Count题目大意思路核心代码 B. Three Threadlets题目大意思路核心代码 C. Perfect Square题目大意思路核心代码 D. Divide and Equalize题目大意思路核心代码 E. Block Sequence题目大意思路核心代码 A. Don’t Try t…...

C# 与 C/C++ 的交互

什么是平台调用 (P/Invoke) P/Invoke 是可用于从托管代码访问非托管库中的结构、回调和函数的一种技术。 托管代码与非托管的区别 托管代码和非托管代码的主要区别是内存管理方式和对计算机资源的访问方式。托管代码通常运行在托管环境中&#xff0c;如 mono 或 java 虚拟机等…...

新版Android Studio搜索不到Lombok以及无法安装Lombok插件的问题

前言 在最近新版本的Android Studio中&#xff0c;使用插件时&#xff0c;在插件市场无法找到Lombox Plugin&#xff0c;具体表现如下图所示&#xff1a; 1、操作步骤&#xff1a; &#xff08;1&#xff09;打开Android Studio->Settings->Plugins&#xff0c;搜索Lom…...

BST二叉搜索树

文章目录 概述实现创建节点查找节点增加节点查找后驱值根据关键词删除找到树中所有小于key的节点的value 概述 二叉搜索树&#xff0c;它具有以下的特性&#xff0c;树节点具有一个key属性&#xff0c;不同节点之间key是不能重复的&#xff0c;对于任意一个节点&#xff0c;它…...

【Leetcode】211. 添加与搜索单词 - 数据结构设计

一、题目 1、题目描述 请你设计一个数据结构&#xff0c;支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 实现词典类 WordDictionary &#xff1a; WordDictionary() 初始化词典对象void addWord(word) 将 word 添加到数据结构中&#xff0c;之后可以对它…...

Discuz户外旅游|旅行游记模板/Discuz!旅行社、旅游行业门户网站模板

价值328的discuz户外旅游|旅行游记模板&#xff0c;本模板需要配套【仁天际-PC模板管理】插件使用。 模板说明 1、模板页面宽度1200px&#xff0c;简洁大气&#xff0c;较适合户外旅行、骑行、游记、摩旅、旅游、活动等类型的论坛、频道网站&#xff1b; 2、所优化的页面有&…...

【重拾C语言】十一、外部数据组织——文件

目录 前言 十一、外部数据组织——文件 11.1 重新考虑户籍管理问题——文件 11.2 文件概述 11.2.1 文件分类 11.2.2 文件指针、标记及文件操作 11.3 打开、关闭文件 11.4 I/O操作 11.4.1 字符读写 11.4.2 字符串读写 11.4.3 格式化读写 11.4.4 数据块读写 11.4.5 …...

dpdk/spdk/网络协议栈/存储/网关开发/网络安全/虚拟化/ 0vS/TRex/dpvs技术专家成长体系教程

课程围绕安全&#xff0c;网络&#xff0c;存储&#xff0c;云原生4个维度去讲解核心技术点。 6个专栏组成&#xff1a;dpdk网络专栏、存储技术专栏、安全与网关开发专栏、虚拟化与云原生专栏、测试工具专栏、性能测试专栏 一、dpdk网络 dpdk基础知识 多队列网卡&#xff0…...

树莓派玩转openwrt软路由:5.OpenWrt防火墙配置及SSH连接

1、SSH配置 打开System -> Administration&#xff0c;打开SSH Access将Interface配置成unspecified。 如果选中其他的接口表示仅在给定接口上侦听&#xff0c;如果未指定&#xff0c;则在所有接口上侦听。在未指定下&#xff0c;所有的接口均可通过SSH访问认证。 2、防火…...

Gin:获取本机IP,获取访问IP

获取本机IP func GetLocalIP() []string {var ipStr []stringnetInterfaces, err : net.Interfaces()if err ! nil {fmt.Println("net.Interfaces error:", err.Error())return ipStr}for i : 0; i < len(netInterfaces); i {if (netInterfaces[i].Flags & ne…...

缓存降级代码结构设计

缓存降级设计思想 接前文缺陷点 本地探针应该增加计数器&#xff0c;多次异常再设置&#xff0c;避免网络波动造成误判。耦合度过高&#xff0c;远端缓存和本地缓存应该平行关系被设计为上下游关系了。公用的远端缓存的操作方法应该私有化&#xff0c;避免集成方代码误操作&…...

一文深入理解高并发服务器性能优化

我们现在已经搞定了 C10K并发连接问题 &#xff0c;升级一下&#xff0c;如何支持千万级的并发连接&#xff1f;你可能说&#xff0c;这不可能。你说错了&#xff0c;现在的系统可以支持千万级的并发连接&#xff0c;只不过所使用的那些激进的技术&#xff0c;并不为人所熟悉。…...

pytorch中的归一化函数

在 PyTorch 的 nn 模块中&#xff0c;有一些常见的归一化函数&#xff0c;用于在深度学习模型中进行数据的标准化和归一化。以下是一些常见的归一化函数&#xff1a; nn.BatchNorm1d, nn.BatchNorm2d, nn.BatchNorm3d&#xff1a; 这些函数用于批量归一化 (Batch Normalization…...

【管理运筹学】第 10 章 | 排队论(1,排队论的基本概念)

文章目录 引言一、基本概念1.1 排队过程1.2 排队系统的组成和特征1.3 排队模型的分类1.4 系统指标1.5 系统状态 引言 开一点排队论的内容吧&#xff0c;方便做题。 排队论&#xff08;Queuing Theory&#xff09;也称随机服务系统理论&#xff0c;是为解决一系列排队问题&…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...