资讯专栏INFORMATION COLUMN

908-最小差值I

KunMinX / 1795人阅读

摘要:前言的第一题最小差值给定一个整数数组,对于每个整数,我们可以选择任意满足,并将加到中。返回的最大值和的最小值之间可能存在的最小差值。

前言

Weekly Contest 103的第一题最小差值I:

给定一个整数数组 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 <= A.length <= 10000

0 <= A[i] <= 10000

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;iA[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;
    }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/77245.html

相关文章

  • Leetcode PHP题解--D18 908. Smallest Range I

    摘要:再向上取整为。第个要向上方求到的靠拢,需要加。最大值和最小值之差为。最终代码若觉得本文章对你有用,欢迎用爱发电资助。 908. Smallest Range I 题目链接 908. Smallest Range I 题目分析 给定一个数组A和一个数字K,找到一个在-K和K之间的数字x并加到数组A中的每一个元素生成数组B,返回数组B中最大值和最小值之差最小的值。 思路 根据题目,需要我们...

    ethernet 评论0 收藏0
  • 164. Maximum Gap

    摘要:这个的长度是最小可能的最大差值。注意考虑和两个边界值也要加进去。 题目:Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time/space. Return 0 if the...

    EddieChan 评论0 收藏0
  • 八大排序算法Java实现

    摘要:向后移动位简单选择排序基本思想常用于取序列中最大最小的几个数时。代码实现循环次数选出最小的值和位置交换位置堆排序基本思想对简单选择排序的优化。 概述 常见的八大排序算法,它们之间的关系如下: showImg(https://segmentfault.com/img/remote/1460000011395738?w=880&h=671); 直接插入排序 希尔排序 简单选择排序 堆排序...

    Coly 评论0 收藏0
  • JavaScript数据结构与算法-Sort-(leetcode原题)

    摘要:说明你可以假设数组中所有元素都是非负整数,且数值在位有符号整数范围内。提示按奇偶排序数组给定一个非负整数数组,中一半整数是奇数,一半整数是偶数。对数组进行排序,以便当为奇数时,也是奇数当为偶数时,也是偶数。 原博客地址:https://finget.github.io/2019... 排序 showImg(https://segmentfault.com/img/remote/146...

    Hanks10100 评论0 收藏0

发表评论

0条评论

KunMinX

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<