摄影师网站推荐,深圳画册设计价格,网站为什么建设中,北京保障性住房建设投资中心网站1. 题目
给定一个整数数组 A#xff0c;对于每个整数 A[i]#xff0c;我们可以选择 x -K 或是 x K#xff0c;并将 x 加到 A[i] 中。
在此过程之后#xff0c;我们得到一些数组 B。
返回 B 的最大值和 B 的最小值之间可能存在的最小差值。
示例 1#xff1a;
输入对于每个整数 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
输出3
解释B [4,6,3]提示
1 A.length 10000
0 A[i] 10000
0 K 10000来源力扣LeetCode 链接https://leetcode-cn.com/problems/smallest-range-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 908. 最小差值 I
首先 都向一侧偏移差值就是max-min部分偏移的话排序以后左侧小的K右侧大的-K才可能得到更小的差值遍历所有的分割点
class Solution { // c
public:int smallestRangeII(vectorint A, int K) {sort(A.begin(), A.end());int i, n A.size(), up, down;int mindis INT_MAX;for(i 0; i n-1; i){up max(A[i]K, A[n-1]-K);down min(A[0]K, A[i1]-K);mindis min(mindis, up-down);}return min(mindis, A[n-1]-A[0]);//第二种情况为同侧偏置}
};68 ms 15 MB
class Solution: # py3def smallestRangeII(self, A: List[int], K: int) - int:A.sort()mindis float(inf)n len(A)for i in range(n-1):up max(A[i]K, A[n-1]-K)down min(A[0]K, A[i1]-K)mindis min(mindis, up-down)return min(mindis, A[n-1]-A[0])# 第二种情况为同侧偏置212 ms 14.9 MB
