新闻详情

新闻详情

首页 / 资讯中心 / 详情

Kimi LeetCode 164.最大间距 Java实现

发布时间:2026/11/16 1:39:51来源:尧图网络
Kimi    LeetCode 164.最大间距 Java实现
LeetCode 164. 最大间距 — Java 实现题目要求返回数组在排序后相邻元素之间的最大差值。要求 O(n) 时间线性时间排序如桶排序。思路一桶排序推荐O(n)O(n)O(n)核心思想排序后的n个数有n-1个间隔。设minVal、maxVal则最大间距的下界为\textit{lowerBound} \left\lceil \frac{\textit{maxVal} - \textit{minVal}}{n - 1} \right\rceil让每个桶的宽度等于lowerBound则同一个桶内的任意两数之差一定小于lowerBound所以最大间距不可能出现在同一个桶内只可能出现在相邻桶之间前一个桶的最大值与后一个桶的最小值之差。importjava.util.Arrays;classSolution{publicintmaximumGap(int[]nums){intnnums.length;if(n2)return0;intminValArrays.stream(nums).min().getAsInt();intmaxValArrays.stream(nums).max().getAsInt();if(minValmaxVal)return0;// 桶宽度 最大间距的下界intbucketSizeMath.max(1,(maxVal-minVal)/(n-1));// 桶数量 数值范围 / 桶宽度 1intbucketCount(maxVal-minVal)/bucketSize1;// 每个桶只记录最小值、最大值、是否为空int[]bucketMinnewint[bucketCount];int[]bucketMaxnewint[bucketCount];boolean[]hasNumnewboolean[bucketCount];for(intnum:nums){intidx(num-minVal)/bucketSize;if(!hasNum[idx]){bucketMin[idx]bucketMax[idx]num;hasNum[idx]true;}else{bucketMin[idx]Math.min(bucketMin[idx],num);bucketMax[idx]Math.max(bucketMax[idx],num);}}// 遍历非空桶计算前一个非空桶的最大值与当前桶的最小值之差intmaxGap0;intprevMaxminVal;for(inti0;ibucketCount;i){if(!hasNum[i])continue;maxGapMath.max(maxGap,bucketMin[i]-prevMax);prevMaxbucketMax[i];}returnmaxGap;}}时间复杂度O(n)空间复杂度O(n)思路二直接排序O(nlog⁡n)O(n \log n)O(nlogn)如果不追求线性时间一行排序即可importjava.util.Arrays;classSolution{publicintmaximumGap(int[]nums){if(nums.length2)return0;Arrays.sort(nums);intmaxGap0;for(inti1;inums.length;i){maxGapMath.max(maxGap,nums[i]-nums[i-1]);}returnmaxGap;}}关键点总结鸽巢原理n个数分布在(max-min)的范围里最大间距至少是(max-min)/(n-1)这是桶宽的来源。为什么只比较相邻非空桶同桶内差值 桶宽 ≤ 答案下界不可能是最优解因此最大间距只可能跨桶产生。桶内只需存 min/max无需真正排序桶内元素。示例nums [3,6,9,1]→ 排序后为[1,3,6,9]最大间距为39-6✅
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/15 4:54:16

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/15 2:04:12

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/16 19:23:38

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/16 6:47:19

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/14 16:35:50

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/16 17:28:18

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉