Самый быстрый способ найти наименьшую возможную сумму абсолютных различий пар в одном массиве? ⇐ Python

[Anonymous]

Группируя все элементы в массив в пары и получая их абсолютные различия, какова минимальная сумма их абсолютных различий? < /p>
Пример: < /p>
[4, 1, 2, 3] should return 2 because |1 - 2| + |3 - 4| = 2
[1, 3, 3, 4, 5] should return 1 because |3 - 3| + |4 - 5| = 1
< /code>
Получить результат для массивов с ровной длиной довольно просто, потому что он просто требует сортировки массива и получения различий между числами рядом друг с другом. < /p>
Тем не менее, массивы с нечетной длиной довольно сложны, потому что добавление дополнительного числа. Таким образом, мое текущее решение для массивов нечетной длины состоит в том, чтобы удалить каждое число и проверить сумму, используя подход массива равномерной.def smallest_sum(arr):
arr = sorted(arr)
if len(arr) % 2 == 0:
return even_arr_sum(arr)
else:
return odd_arr_sum(arr)

def even_arr_sum(arr):
total = 0
for i in range(0, len(arr), 2):
total += arr[i+1] - arr
return total

def odd_arr_sum(arr):
total = 0
for i in range(len(arr)):
s = even_arr_sum(arr[:i] + arr[i+1:])
if total == 0 or s < total:
total = s
return total

assert smallest_sum([4, 1, 2, 3]) == 2
assert smallest_sum([1, 3, 3, 4, 5]) == 1
< /code>
Однако это очень медленно и дает время N2. Есть ли более разумный способ обработки массивов с нечетной длиной?

Подробнее здесь: https://stackoverflow.com/questions/793 ... ces-of-pai