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

Question

[AniArim]

Прошу помочь решить задачу или хотя бы намекнуть, в какую сторону "копать". Дан массив целых чисел. Необходимо найти минимальное количество ходов, требуемых для приведения всех элементов массива к одному числу. За один ход можно уменьшить или увеличить один элемент массива на 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

[Михаил Кростелев]

Ищите медиану вашего набора чисел. Это и будет отправная точка, до которой нужно будет добивать все числа.
А дальше просто суммируете модули разности каждого элемента набора с этим числом.
Если нужно более подробно - скажите

P.S. Перечитал второй ответ - в принципе то же самое.

Comments

[AniArim]

Я поняла это, прочитав комментарии и ваш пример с тысячей. Позже добавлю код. Буду благодарна, если скажете какой материал почитать, чтобы подтянуть теорию. А то, понять что делать - поняла, а почему - нет.

[Михаил Кростелев]

AniArim, ну вообще это из области статистики.
Тот случай когда нельзя брать среднее значение, т.к. есть значения сильно выбивающиеся из общей массы.
Очень похоже на подсчет средней зарплаты в городах, когда разрыв между бедными и богатыми очень большой.
Одни едят капусту, другие мясо. В среднем все едят голубцы.
Это неправильный вариант подсчета.

[U235U235]

import numpy as np
a=np.array([4,4,4,7])
print(np.sum(np.abs(a-np.median(a))))

Answer 2

[Wataru]

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

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

Теперь вам надо посмотреть, подумать и выбрать оптимальное X, которому вы будете приводить все числа. Ваш вариант с max/2 не оптимален.

Comments

[AniArim]

Спасибо большое!
Код теперь выглядит так, возможно вы не это имели ввиду, но результат выдает нужный.

count = 0
nums_result = [int(i) for i in nums]
    result_digit = sum(nums_result) // len(nums_result)
    for item in nums_result:
        if item < result_digit:
            count += (result_digit - item)
        elif item > result_digit:
            count += item - result_digit
        else:
            pass
    print(count)

[Михаил Кростелев]

AniArim, проверьте этот код например на варианте [1, 1, 1, 1, 1000]
Что выведет?

[AniArim]

Михаил, 1596, это верный ответ)?

[Михаил Кростелев]

AniArim, а ведь мы можем просто 999 раз уменьшить тысячу на единицу.

[Wataru]

AniArim, Вам уже ниже сказали - надо в качестве цели выбрать медиану всех чисел. Потому что при сдвиге цели на 1 вправо вы прибавляете столько, сколько числел слева и вычитаете столько, сколько чисел справа. Поэтому, если справа чисел больше, чем слева - то надо двигаться вправо и т.д. В итоге остановимся или на среднем числе (если их нечетно) или можно выбрать любое число из интервала между двумя средними (если чисел в массиве четное количество).

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

Answer 3

[Alexandroppolus]

Надо найти сумму всех abs(a[i] - Х), где X - то самое число, которое окажется посередине, если массив отсортировать (то есть медиана).
Оное число, если не ошибаюсь, можно найти линейно с помощью QuickSelect. Если массив нельзя перемешивать, придется сделать его копию.

Comments

[Михаил Кростелев]

Зачем там QuickSelect? Отсортировали, поделили количество элементов на 2, получили индекс по которому получим нашу медиану.

[Alexandroppolus]

Михаил, сложность сортировки O(N*ln(N)), а сложность поиска медианы - O(N).
Я понимаю, что у автора вопроса наверняка массив не такой длинный, чтобы это могло как-то зарешать, но тем не менее.

[Михаил Кростелев]

Alexandroppolus, Если задаваться вопросом скорости работы и сложности О, тогда да.

Answer 4

[Сергей Соколов]

Визуально можно представить: на плоскоть бросили случайно кучку точек )
Оси X и Y, приём X не важен в данном случае. Y – значения в массиве.

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

Это упрощённый вариант линейной регрессии, кстати.

Answer 5

[Akina]

Если количество элементов массива нечётно, то тем значением, к которому надо привести элементы, равно значению строго среднего элемента (медианы массива).

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

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