Уровень: medium
Решаю задачки на массивы, делюсь интересной.
Условие следующее: дан массив целых чисел размером n, требуется вернуть минимальное количество шагов, необходимых для того, чтобы все элементы массива стали равны. За один шаг можно увеличить 'n - 1' элементов массива на 1.
Например, дан массив:
[3,1,4]
- шаг 1: [3,2,5] - увеличили 1-ый, и 2-ой элементы
- шаг 2: [4,3,5] - увеличили 0-ой, и 1-ый элементы
- шаг 3: [5,4,5] - увеличили 0-ой, и 1-ый элементы
- шаг 4: [6,5,5] - увеличили 0-ой, и 1-ый элементы
- шаг 5: [6,6,6] - увеличили 1-ый, и 2-ой элементы
Минимальное количество шагов, которое потребуется в данном случае, чтобы все элементы массивы стали равны - это 5.
Алгоритм: для того, чтобы решить задачу, нужно посмотреть на нее под другим углом. Увеличивать 'n-1' элементов массива на 1 это равносильно тому, что уменьшать на 1 один элемент массива. Другими словами, задача сводится к тому, чтобы привести все элементы массива к минимальному значению.
Проверим на том же массиве - [3,1,4]:
- шаг 1: [3,1,3] - уменьшаем 2-ой
- шаг 2: [3,1,2] - уменьшаем 2-ой
- шаг 3: [3,1,1] - уменьшаем 2-ой
- шаг 4: [2,1,1] - уменьшаем 0-ой
- шаг 5: [1,1,1] - - уменьшаем 0-ой
Ответ: 5
Значит, нам нужно выполнить следующие шаги в алгоритме:
1. Найти минимальное значение в массиве
2. Найти разницу между каждым элементом и минимальным значением
3. Суммировать все разницы - это и будет минимальное количество шагов, которое требуется для того, чтобы все элементы стали равны.
Итак, код:
public int minMoves(int[] nums) {
int min = Integer.MAX_VALUE;
for (int num: nums) {
min = Math.min(num, min);
}
int moves = 0;
for (int num: nums) {
moves += num - min;
}
return moves;
}Временная сложность: O(n) т.к. O(n) - для нахождения минимального элемента в массиве и O(n) - для подсчета общего кол-ва шагов.
Пространственная сложность: O(1), т.к. требуется фиксированное количество памяти для хранения минимального значения массива и для количества шагов.