@AniArim

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

Прошу помочь решить задачу или хотя бы намекнуть, в какую сторону "копать". Дан массив целых чисел. Необходимо найти минимальное количество ходов, требуемых для приведения всех элементов массива к одному числу. За один ход можно уменьшить или увеличить один элемент массива на 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. Массив может быть любой длинны.
  • Вопрос задан
  • 2382 просмотра
Пригласить эксперта
Ответы на вопрос 5
@twistfire92
Python backend developer
Ищите медиану вашего набора чисел. Это и будет отправная точка, до которой нужно будет добивать все числа.
А дальше просто суммируете модули разности каждого элемента набора с этим числом.
Если нужно более подробно - скажите

P.S. Перечитал второй ответ - в принципе то же самое.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Во-первых, в вашем алгоритме цикл while вообще не нужен. Сколько нужно операций +1, чтобы из a получить a+12345? Ровно 12345. Вам надо просто вычесть одно число из другого.

Далее, мысль должна быть такая: Вот вы знаете, сколько нужно операций, чтобы все числа в массиве привести к X. Вопрос: сколько операций вам понадобится для приведения всех чисел к X+1? (Подсказка - если число было меньше X, то теперь понадобится на 1 операцию больше. Если число было больше X - то понадобится на 1 операцию меньше).

Теперь вам надо посмотреть, подумать и выбрать оптимальное X, которому вы будете приводить все числа. Ваш вариант с max/2 не оптимален.
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
Надо найти сумму всех abs(a[i] - Х), где X - то самое число, которое окажется посередине, если массив отсортировать (то есть медиана).
Оное число, если не ошибаюсь, можно найти линейно с помощью QuickSelect. Если массив нельзя перемешивать, придется сделать его копию.
Ответ написан
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Визуально можно представить: на плоскоть бросили случайно кучку точек )
Оси X и Y, приём X не важен в данном случае. Y – значения в массиве.

Нужно так подвинуть горизонтальную линию, чтобы сумма расстояний от каждой из точек до этой линии оказалась минимальна. Её Y и будет тем значением, до которой остальным точкам «шагать».

Это упрощённый вариант линейной регрессии, кстати.
Ответ написан
Комментировать
@Akina
Сетевой и системный админ, SQL-программист.
Если количество элементов массива нечётно, то тем значением, к которому надо привести элементы, равно значению строго среднего элемента (медианы массива).

Если количество элементов массива чётно, то в качестве конечного значения подходит любое значение между двумя средними элементами, включительно.

Для того, чтобы убедиться в этом - просто подумай, как изменяется требуемое количество шагов выравнивания, если двигать конечное значение на 1 вправо или влево, в зависимости от того, сколько элементов справа и сколько слева.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы