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

ethernet 发布于2019-07-01 12:38 / 3276人阅读

摘要：再向上取整为。第个要向上方求到的靠拢，需要加。最大值和最小值之差为。最终代码若觉得本文章对你有用，欢迎用爱发电资助。

908. Smallest Range I 题目链接

908. Smallest Range I

题目分析

给定一个数组A和一个数字K，找到一个在-K和K之间的数字x并加到数组A中的每一个元素生成数组B，返回数组B中最大值和最小值之差最小的值。

思路

根据题目，需要我们可以给数组A中的每一个元素添加-K<=x<=K中的任何一个整数，使新生成的数组B的最大值和最小值之差最小。

怎么使最大值和最小值之差最小呢？
最大值和最小值越接近中间值，最大值和最小值之差最小。

举个例子：A = [-3, 1, 3, 5, 4, 6], K = 3

先求中间值：$mid = ceil((max($A)+min($A))/2)。(-3+6)/2再向上取整为2。

再遍历每个元素。

第0个：-3要向上方求到的2靠拢，需要加2-(-3)=5。然而5>(K=3)。那么只能加K的最大值3了。-3+3=0；

第1个：1要向2靠拢，需要1，-K<=1<=K，1+1=2；

第2个：3，-K<=-1<=K，3-1=2；

第3个：5，-K<=-3<=K，5-3=2；

第4个：4，-K<=-2<=K，4-2=2；

第5个：6，-4<(-K=3)，取最小值-3，6-3=3。

我们于是得到数组B = [0,2,2,2,2,3]。最大值和最小值之差为3-0=3。

最终代码

$K && $a>=$mid){
                $b[] = $a-$K;
            }
            else if($a-$mid<$K&&$a>=$mid){
                $b[] = $mid;
            }
            else if($mid-$a<$K && $a<$mid){
                $b[] =$mid;
            }
            else if($mid-$a>$K && $a<$mid){
                $b[] = $a+$K;
            }
        }
        return max($b)-min($b);
    }
}

若觉得本文章对你有用，欢迎用爱发电资助。

海外云主机服务器托管 Smallest 题解 oj题解 LeetCode

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

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

Leetcode PHP题解--D79 448. Find All Numbers…

摘要：题目链接题目分析给定一个到的数组，返回其中缺失的数字。思路用得出到的数字，再用和给定的数组计算差集。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D79 448. Find All Numbers Disappeared in an Array 题目链接 448. Find All Numbers Disappeared in an Array 题目分析给定一个1到n的数组，返回...

X1nFLY 2019-07-01 13:57 评论0 收藏0
Leetcode PHP题解--D71 788. Rotated Digits

摘要：题目链接题目分析当一个数字度旋转后，不等于原来的数字，那么我们称它是一个好数字。和旋转后为对方。思路用函数生成到给定数组之间的所有数组。对每一个数字，用和函数处理。对数字，转换成。否则返回，排除当前数字。 D71 788. Rotated Digits 题目链接 788. Rotated Digits 题目分析当一个数字180度旋转后，不等于原来的数字，那么我们称它是一个好数字。例...

CntChen 2019-07-01 12:50 评论0 收藏0
Leetcode PHP题解--D10 942. DI String Match

摘要：题目链接题目分析给定一个只含和的字符串，返回一个数组。这个数组满足以下条件当为时，。当遇到时，在数组的当前下标位置前插入当前下标。最终代码个人认为这题不是很好描述。有空会尝试描述清楚这个问题。 942. DI String Match 题目链接 942. DI String Match 题目分析给定一个只含I和D的字符串S，返回一个数组。这个数组满足以下条件：当S[i]为I时...

yibinnn 2019-07-01 12:35 评论0 收藏0
Leetcode PHP题解--D52 496. Next Greater Element I

摘要：题目链接题目分析给定两个数组，其内元素不重复。数组是数组的子集，返回每个在数组中的元素在数组对应位置以右最大的元素。思路只能逐个遍历吧。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D52 496. Next Greater Element I 题目链接 496. Next Greater Element I 题目分析给定两个数组，其内元素不重复。数组1是数组2的子集，返回每个...

only_do 2019-07-01 12:44 评论0 收藏0
Leetcode PHP题解--D14 561. Array Partition I

摘要：题目链接题目分析本题给了一个数组，要求将数组分为个只有个元素的一对。因此，要使每组中最大的数字和最小的数组之差最小，这样才能使损失最小。当分为两组时，每组取最小后，会得到。求和后为，比大。 561. Array Partition I 题目链接 561. Array Partition I 题目分析本题给了一个数组，要求将数组分为n个只有2个元素的一对。使得每对数字中最小的数加起...

stonezhu 2019-07-01 12:36 评论0 收藏0