Сложность: 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, что и будет конечным результатом.
😎 Решение:
class Solution {
public function minMoves2($nums) {
$ans = PHP_INT_MAX;
$minval = min($nums);
$maxval = max($nums);
for ($i = $minval; $i <= $maxval; $i++) {
$sum = 0;
foreach ($nums as $num) {
$sum += abs($num - $i);
}
$ans = min($ans, $sum);
}
return (int) $ans;
}
}Ставь 👍 и забирай 📚 Базу знаний