给你一个整数数组 nums
,和一个整数 k
。
对于每个下标 i
(0 <= i < nums.length
),将 nums[i]
变成 nums[i] + k
或 nums[i] - k
。
nums
的 分数 是 nums
中最大元素和最小元素的差值。
在更改每个下标对应的值之后,返回 nums
的最小 分数 。
示例 1:
输入:nums = [1], k = 0 输出:0 解释:分数 = max(nums) - min(nums) = 1 - 1 = 0 。
示例 2:
输入:nums = [0,10], k = 2 输出:6 解释:将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。
示例 3:
输入:nums = [1,3,6], k = 3 输出:3 解释:将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。
分析:与908 最小差值 I 类似,只是这次的数组必须选择 + k 或者 - k。思路也与908类似,让小的值变大,大的值变小。但是由于数组的每个值都需要变化,可能存在交叉的情况,即数组中间的某个值+k之后比最大值-k要大。为了解决这种情况,我们可以枚举分界点,在分界点左边的值+k,右边的-k。
int cmp(const void *a,const void *b)
{int *aa=(int*)a;int *bb=(int*)b;return *aa-*bb;
}
int smallestRangeII(int* nums, int numsSize, int k) {qsort(nums,numsSize,sizeof(nums[0]),cmp);int ans=nums[numsSize-1]-nums[0];for(int i=numsSize-1;i>0;--i)//枚举分界点{//注意每个分界点还要比较分界点的前一个点的情况是否会出现交叉if(nums[i]-k>nums[0]+k)ans=fmin(ans,fmax(nums[numsSize-1]-k,nums[i-1]+k)-nums[0]-k);else ans=fmin(ans,fmax(nums[numsSize-1]-k,nums[i-1]+k)-nums[i]+k);}return ans;
}