博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
908-最小差值I
阅读量:5867 次
发布时间:2019-06-19

本文共 1227 字,大约阅读时间需要 4 分钟。

前言

的第一题:

给定一个整数数组 A,对于每个整数 A[i],我们可以选择任意 x 满足 -K <= x <= K,并将 x 加到 A[i] 中。

在此过程之后,我们得到一些数组 B。

返回 B 的最大值和 B 的最小值之间可能存在的最小差值。

示例 1:

输入:A = [1], K = 0输出:0解释:B = [1]

示例 2:

输入:A = [0,10], K = 2输出:6解释:B = [2,8]

示例 3:

输入:A = [1,3,6], K = 3输出:0解释:B = [3,3,3] 或 B = [4,4,4]

提示:

  1. 1 <= A.length <= 10000
  2. 0 <= A[i] <= 10000
  3. 0 <= K <= 10000

解题思路

这里介绍我的最终解题思路前,先要解读一下题目的要求。

首先解读一下题目的要求,这个题目的意思是给数组A中的每个元素A[i]都与x相加(x的取值范围为[-K,K],需要注意每个和A[i]x可以不相同),这样获得一个数组B,然后取出B中的最大值和最小值相减获得差值。由于B存在很多个,需要找去其中的差值最小的情况。这里补充一点题目没有提到的,差值是要取绝对值的,也就是差值的最小值为0。

一看完这个题目的时候,我第一个解题的思路是模拟选择x的过程,然后求出最小差值,也就是所谓的暴力破解。但是仔细想了一下,因为x 满足 -K <= x <= K,如果要模拟这个过程的话,必然会因为部分测试用例的整数数组 A长度很大而出现执行超时,而且暴力破解这个方法也不够优雅。

后面思考了一下,既然是求最大值和最小值的差值,为什么不先求出原数组A的最大值和最小值的差值range,然后再对range进行两次和x的求和获得最小差值呢?需要注意这两次求和都是对0的逼近。

实现代码

public int smallestRangeI(int[] A, int K) {        int max=0;        int min=Integer.MAX_VALUE;        for(int i=0;i
A[i]){ min=A[i]; } } int range=max-min; int times=2; while(times>0){ if(range>0){ if(range>K){ range-=K; }else{ range=0; } } --times; } return range; }

转载地址:http://ionnx.baihongyu.com/

你可能感兴趣的文章
Object类有哪些方法
查看>>
6月8日任务 Nginx访问日志、Nginx日志切割、静态文件不记录日志和过期时间
查看>>
MySQL主从知识扩展
查看>>
Spring Cloud云服务 - HongHu架构common-service 项目构建过程
查看>>
闪电侠netty
查看>>
云栖专辑| 阿里毕玄:程序员的成长路线
查看>>
阿里云数据库自研产品亮相国际顶级会议ICDE 推动云原生数据库成为行业标准...
查看>>
ajax常用到的几种使用
查看>>
阿里Java程序员必备的Intellij IDEA 插件
查看>>
TechDay实录|摘取皇冠上的明珠,中文NLP的不二选择——PaddlePaddle
查看>>
C++中如何中止accept
查看>>
Windows to Windows SSH登录
查看>>
多年的人工智能安全机制争议 检察官、行刑者与道德家这么表示
查看>>
Java实现单点登录
查看>>
PHP使用flock实现文件加锁的方法
查看>>
OSChina 周六乱弹 —— 鬼节最怕碰见什么鬼?
查看>>
OSChina 周一乱弹 ——程序员是时候改变下自己的形象
查看>>
OSChina 周日乱弹 —— 不许看猫片啦!身体都看坏了!
查看>>
SSH免密码登录,
查看>>
BufferedOutputStream 源码学习
查看>>