908-最小差值I

KunMinX 发布于2019-08-19 11:14 / 1655人阅读

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

前言

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

服务器托管 GPU服务器日期差值差值 python求差值 java 计算日差值

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

转载请注明本文地址：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 2019-07-01 12:38 评论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 2019-08-14 14:09 评论0 收藏0
八大排序算法Java实现

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

Coly 2019-08-15 11:57 评论0 收藏0
JavaScript数据结构与算法-Sort-(leetcode原题)

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

Hanks10100 2019-08-23 18:08 评论0 收藏0