Минимальная разница между наибольшим и наименьшим элементом после 3 шагов

-

Источник: https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/

Дан массив целых чисел nums. За один ход можно выбрать один элемент изnums и заместить его на любой другой элемент массива.

Вернуть минимальную разность между самым большим и самым маленьким элементом из nums за не более 3 шагов.

Пример 1:

Дано: nums = [5,3,2,4]
Результат: 0
Поянение: Исходный массив [5,3,2,4] превращаем в [2,2,2,2].
Разница между минимальным и максимальным значением: 2-2 = 0.

Пример 2:

Дано: nums = [1,5,0,10,14]
Результат: 1
Explanation: Исходный массив [1,5,0,10,14] превращаем в [1,1,0,1,1]. 
Разница между минимальным и максимальным значением: 1-0 = 1.

Ограничения:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Идея решения

Если у нас 0 шагов, мы вернем max(A) - min(A)
Если у нас 1 шаг, мы вернем min(the second max(A) - min(A), the max(A) - second min(A))
и так далее.

Поскольку у нас не более 3 шагов, то у нас есть 4 варианта развития событий:

  1. убрать 3 наибольших элемента
  2. убрать 2 наибольших элемента + 1 наименьший элемент
  3. убрать 1 наибольший элемент + 2 наименьших элемента
  4. убрать 3 наименьших элемента

Например:

A = [1,5,6,13,14,15,16,17]
n = 8

План 1: убрать 3 наибольших элемента

Заместим все 3 наибольших элемента на 14
[1,5,6,13,14,15,16,17] -> [1,5,6,13,14,14,14,14] ==>  результат: A[n-4]-A[0] == (14-1 = 13)

План 2: убрать 2 наибольших элемента + 1 наименьший элемент

[1,5,6,13,14,15,16,17] -> [5,5,6,13,14,15,15,15] ==>  результат: A[n-3]-A[1] == (15-5 = 10)

План 3: убрать 1 наибольший элемент + 2 наименьших элемента

[1,5,6,13,14,15,16,17] -> [6,6,6,13,14,15,16,16]  ==>  результат:A[n-2]-A[2] == (16-6 = 10)

План 4: убрать 3 наименьших элемента

[1,5,6,13,14,15,16,17] -> [13,13,13,13,14,15,16,17] ==>  результат:  A[n-1]-A[3] == (17-13 = 4)

А финальный результат: минимум среди всех этих 4 планов.

Имплементация 

class Solution {
     public int minDifference(int[] A) {
        int n = A.length, res = Integer.MAX_VALUE;
        if (n < 5) return 0;
// поскольку массив после 3 шагов будет состоять из одинаковых элементов

        Arrays.sort(A);
        for (int i = 0; i < 4; ++i) {
            res = Math.min(res, A[n - 4 + i] - A[i]);
        }
        return res;
    }
}

Комментарии

Отправить комментарий