0910. Smallest Range II (M)

Smallest Range II (M)

题目

Given an array A of integers, for each integer A[i] we need to choose either x = -K or x = K, and add x to A[i] (only once).

After this process, we have some array B.

Return the smallest possible difference between the maximum value of B and the minimum value of B.

Example 1:

Input: A = [1], K = 0
Output: 0
Explanation: B = [1]

Example 2:

Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]

Example 3:

Input: A = [1,3,6], K = 3
Output: 3
Explanation: B = [4,6,3]

Note:

1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000

题意

遍历一个数组，对每个值进行加K或减K的操作，求得到的新数组中(max-min)的最小值。

思路

因为每个元素都必须加K或者减K，可以将数组分成两组，一组全加K，一组全减K，很明显要让小的数加K，让大的数减K。因此可以先对数组排序，然后确定一个分界点，让左边的子数组left全部加K，右边的子数组right全部减K；同时注意到，两个子数组中的最小值都是各自的第一个元素，最大值都是各自的最后一个元素，因此可以比较得出全局的最大值和最小值，再以此更新结果。

代码实现

Java

class Solution {
    public int smallestRangeII(int[] A, int K) {
        int ans = Integer.MAX_VALUE;
        Arrays.sort(A);

        for (int len = 0; len <= A.length; len++) {
            int max = 0, min = 0;
            if (len == 0 || len == A.length) {
                max = A[A.length - 1];
                min = A[0];
            } else  {
                max = Math.max(A[len - 1] + K, A[A.length - 1] - K);
                min = Math.min(A[0] + K, A[len] - K);
            }
            ans = Math.min(ans, max - min);
        }

        return ans;
    }
}