Алгоритм поиска минимального количества ходов, требуемых для приведения всех элементов к одному числу (Python)

Question

Прошу помочь решить задачу или хотя бы намекнуть, в какую сторону "копать". Дан массив целых чисел. Необходимо найти минимальное количество ходов, требуемых для приведения всех элементов массива к одному числу. За один ход можно уменьшить или увеличить один элемент массива на 1. Все достаточно просто пока массив выглядит вот так:

`
import math


nums = [1, 10, 2, 9]
result_digit = math.ceil((max(nums))/2)
count = 0
for id, i in enumerate(nums):
    while i != result_digit:
        if i < result_digit:
            i += 1
            count += 1
         elif i > result_digit:
             i -= 1
             count += 1
         else:
            nums[id] = i
    print(count)
`

Но, если nums = [0, 0, 0, 1], тогда этот алгоритм не подходит и выведет результат 3 вместо 1. Массив может быть любой длинны.

Answer 1

Ну, во-первых округлять нужно с помощью round, у вас получается не оптимальное округление, не к ближайшему целому. А во-вторых - почему max/2? Приводить нужно к среднему арифметическому:

result_digit = round(sum(nums)/len(nums))

Можете проверить на примере, где все числа далеки от нуля. Ваш вариант начнёт приводить куда-то вообще не туда. Например, если взять:

nums = [9, 9, 9, 10]

Ваш вариант начнёт приводить всё к 10/2, т.е. 5, а не к округлённому среднему 9, как было бы оптимально.

Answer 2

Посмотрим на задачу с конца. Если мы как-то узнали значение m к которому нужно привести массив, то сколько на это уйдет шагов? Для одного элемента массива a[i] потребуется abs(a[i] - m) шагов. Для всего массива sum(abs(v - m) for v in a).

Известно что минимум суммы выше будет достигаться если m медиана a. Медиан может быть много. Одна из медиан - средний элемент массива после его сортировки.

a = [1, 10, 2, 9]
m = sorted(a)[len(a) // 2]
print(sum(abs(v - m) for v in a))

БЛОГ НА HUSL

Алгоритм поиска минимального количества ходов, требуемых для приведения всех элементов к одному числу (Python)

Ответы (2 шт):