Сложность: 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:
def minMoves2(self, nums: List[int]) -> int:
ans = float('inf')
minval = min(nums)
maxval = max(nums)
for i in range(minval, maxval + 1):
sum_moves = 0
for num in nums:
sum_moves += abs(num - i)
ans = min(ans, sum_moves)
return int(ans)
Ставь 👍 и забирай 📚 Базу знаний