Сложность: medium
Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.
В одном ходе вы можете увеличить или уменьшить элемент массива на 1.
Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.
Пример:
Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3] => [2,2,3] => [2,2,2]
👨💻 Алгоритм:
1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива.
2⃣Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k.
3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом.
😎 Решение:
public class Solution {
public int minMoves2(int[] nums) {
long ans = Long.MAX_VALUE;
int minval = Integer.MAX_VALUE;
int maxval = Integer.MIN_VALUE;
for (int num : nums) {
minval = Math.min(minval, num);
maxval = Math.max(maxval, num);
}
for (int i = minval; i <= maxval; i++) {
long sum = 0;
for (int num : nums) {
sum += Math.abs(num - i);
}
ans = Math.min(ans, sum);
}
return (int) ans;
}
}Ставь 👍 и забирай 📚 Базу знаний