Оптимизировать код для минимального количества свопов

Question

Вам дан неупорядоченный массив, состоящий из последовательных целых чисел [1, 2, 3, ..., n] без дубликатов.Вы можете поменять местами любые два элемента.Вам нужно найти минимальное количество перестановок, необходимое для сортировки массива в порядке возрастания.Код, который я получил, рассчитан на несколько тестовых случаев. Есть ли способ оптимизировать код?

Мой код выглядит следующим образом:

def minimumSwaps(arr):
    lst=[ele+1 for ele in range(len(arr))]
    cnt=0
    for i in range(len(arr)):
        if(lst[i]!=arr[i]):
            k=arr.index(lst[i])
            arr[i],arr[k]=arr[k],arr[i]
            cnt=cnt+1
    return cnt

Answer 1

Вам не нужно создавать список ссылок lst, потому что вы должны знать, что n в arr должно быть в индексе n-1 для повышения.Кроме того, выполнение k=arr.index(lst[i]) требует O(n) времени для поиска, а это совершенно не нужно.Вот мое решение:

def minimumSwaps(arr):
    total_swaps = 0
    start = 0
    while start < len(arr):
        if arr[start] == start + 1:
            start += 1
            continue
        arr[arr[start] - 1], arr[start] = arr[start], arr[arr[start] - 1]
        total_swaps += 1
    return total_swaps

Если я угадаю, что это правильно, это вопрос к Hackerrank, и это было мое решение к тому времени, когда прошли тесты.: Р