Минимальные ходы, необходимые для отдельного массива ⇐ Python

[Anonymous]

Вам дают массив, содержащий n целых чисел, где каждое целое число находится в диапазоне [1..n]. В каждом шаге вы можете увеличить или уменьшить значение любого элемента на 1 с ограничением того, что после каждого хода все числа должны оставаться в диапазоне [1..n]. Ваша цель состоит в том, чтобы определить минимальное количество движений, необходимых для обеспечения того, чтобы все элементы в массиве были различны, что означает, что ни одно число не появляется в массиве. /> Решение ([6, 2, 3, 5, 6, 3]) -> Возвращает 4 < /p>
Решение ([1, 2, 1]) -> Возвращает 2 < /p>
Решение ([2, 1, 4, 4]) -> Возвращает 1 < /p>
Добавление моего решения в Python. [2,1,5,5] Потому что я предполагаю, что целевой массив с числами как индекс + 1, что может быть правильным предположением.
нужно написать эффективное решение. < /P>
def solution(A, changes = 0):
# Step 1: Sort the array to align the elements in increasing order
A.sort()
# Step 2: Loop through the sorted array to calculate the 'changes' required
for i in range(len(A)):
# The expected value at index i is (i + 1), because we want the array to be [1, 2, 3, ...]
# Calculate the absolute difference between the sorted value and the expected value
changes += abs(A - (i + 1))
# Step 3: Return the total number of changes
return changes
# Test cases
print(solution([6, 2, 3, 5, 6, 3])) # Should return 4
print(solution([1, 2, 1])) # Should return 2
print(solution([2, 1, 4, 4])) # Should return 1


Подробнее здесь: https://stackoverflow.com/questions/795 ... inct-array