当前位置：首页 > article >正文

LeetCode 每日一题最小差值 II

article 2024/10/22 5:27:15

最小差值 II

给你一个整数数组 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 。
提示：
1 <= nums.length <= 104
0 <= nums[i] <= 104
0 <= k <= 104

题解

题目要求操作后的数组的最大与最小的差值，返回所有操作中能达到的最小的差值

由于题目要求对所有的元素都要进行操作，所以我们操作的想法是：

将小的数 +k

大的数 -k

至于如何判断什么是小的数，也就是说哪些数要 +k

由于数组中的数据是不确定的

所以我们对于要 +k 的数进行枚举

找到其中的最小 max-min 作为返回值

为了便于之后的操作，我们先将数组进行排序

对于每一个具体的枚举

假设此时下标为 0 到 i 的数组元素进行 +k，剩下的 -k

(实际上我们并不对数组进行操作)

那么操作之后的数组中的最大值是

nums[i] + k 与 nums[numsSize-1] - k 中最大的

即最大的 +k的以及最大的 -k的之间的最大的

同理可知最小值是

nums[0]+k 与 nums[i+1]-k 中最小的

然后记录下所有枚举中的最大值 - 最小值的最小值res

就是返回值

代码如下↓

int smallestRangeII(int* nums, int numsSize, int k) {
    int cmp(const void* a,const void* b)
    {
        return *(int*)a - *(int*)b;
    }
    qsort(nums,numsSize,sizeof(int),cmp);
    int res=nums[numsSize-1] - nums[0];
    for(int i=0;i<numsSize-1;i++)
    {
        int max = nums[i]+k > nums[numsSize-1]-k ? nums[i]+k : nums[numsSize-1]-k;
        int min = nums[0]+k < nums[i+1]-k ? nums[0]+k : nums[i+1]-k;
        if(max - min < res)
        {
            res = max - min;
        }
    }
    return res;
}