Preface explains

Algorithm learning, daily brush record.

Subject to connect

Minimum difference I

The subject content

Given an array of integers A, add an arbitrary number x(-k <= x <= K) to each element of the array A[I] to create A new array B.

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

Example 1:

Input: A = [1], K = 0

Output: 0

Explanation: B = [1]

Example 2:

Input: A = [0,10], K = 2

Output: 6

B = [2,8]

Example 3:

Input: A = [1,3,6], K = 3

Output: 0

B = [3,3,3] B = [4,4,4]

Tip:

1 <= A.length <= 10000

0 <= A[i] <= 10000

0 <= K <= 10000

The analysis process

Walk through group A to find the minimum and maximum.

If the difference between the maximum and minimum of array A is less than or equal to 2 times k, then the minimum of array A can move n1 bits, and the maximum can move N2 bits, where the absolute values of n1 and n2 are less than or equal to k.

We can always make the maximum and minimum of array A equal, and as long as n1 and n2 have more points and less points, we can make the maximum and minimum equal, so the minimum difference of array B is 0.

If the difference between the maximum and the minimum of ARRAY A is greater than 2 times that of k, then the minimum of array A plus k, the maximum minus k, the maximum and the minimum close together, you get the minimum of array B.

Because the difference is greater than 2 times k, there is no crossover even if the minimum and maximum are both moved by K, and the minimum difference is exactly equal to max-min-k * 2.

To solve the code

Class Solution {public int smallestRangeI(int[] A, int K) {int min = A[0], Max = A[0]; For (int e: A) {if (e < min) {// Update min = e; } if (e > Max) {// Update Max = e; }} if (max-min <= K * 2) {// If (max-min <= K * 2) {// If (max-min <= K * 2) {// If (max-min <= K * 2) {// If (max-min <= K * 2) {// If (max-min <= K * 2) {// If (max-min <= K * 2) { So the minimum difference of array B is 0 return 0; Return max-min-k * 2; return max-min-k * 2; return max-min-k * 2; return max-min-k * 2; }}}Copy the code

Submit the results

The execution time was 1ms, beating 100.00% user time, 38.9MB memory consumption, and beating 26.89% user space.

The original link

Minimum difference I