Тайм-аут сортировки массивов для массивов огромного размера

Question

Я участвую в онлайн-тестировании кода. У меня есть массив, который мне нужно отсортировать и записать до минимального количества итераций, необходимых для сортировки. У меня есть следующий код.

def minSwap(ar):
    c = 0

    for i in range(0, len(ar)):
        if ar[i] == i+1:
            continue
        else:
            for k in range(i+1, len(ar)):
                if ar[k] == i+1:
                    ar[k] = ar[i]
                    ar[i] = i+1
                    c = c+1
                    break
    return c

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

Может ли кто-нибудь помочь определить неисправный блок кода, который я делаю неправильно, я не вижу способа его подправить?

Answer 1

На самом деле вам не нужно выполнять сортировку по этому массиву. Вам просто нужно выяснить минимальное количество необходимых свопов. Если мы просто посмотрим на следующий шаблон, мы можем сформировать гипотезу, которую нужно проверить:

• 1234 = 0
• 1324 = 1, поменять местами 2 и 3
• 1423 = 2, поменять местами 2 и 4, поменять местами 3 и 4
• 4213 = 2, поменять местами 1 и 4, поменять местами 3 и 4
• 4123 = 3, поменять местами 4 и 1, поменять местами 4 и 2, поменять местами 4 и 3

Основываясь на этих наблюдениях, я думаю, что мы можем работать над гипотезой о том, что ответ будет max (0, n - 1), где n - количество "неуместные" элементы.

Затем код упрощается до:

def minSwap(ar):
    c = 0

    for i in range(0, len(ar)):
        if ar[i] != i+1:
            c = c + 1
    return c < 0 ? 0 : c

Обратите внимание, что я на самом деле не знаю python, поэтому не знаю, является ли эта последняя тройка действует в python.

Answer 2

Глядя на формулировку проблемы, похоже, что вы хотите отсортировать список, в котором номера начинаются с 1 по n.

Если вы пытаетесь отсортировать список, и ожидается, что окончательный список будет [1, 2, 3, 4, 5, 6, 7 , 8, .....], тогда все, что вам нужно сделать, это вставить i+1 в текущую позицию и извлечь значение i+1 из его текущей позиции. Это уменьшит количество итераций, которые вам нужно сортировать или поменять местами.

Вот код, который делает это с наименьшим количеством ходов. По крайней мере, это то, что я обнаружил на основе своих тестов.

def minSwap(ar):
    c=0
    for i in range(0, len(ar)):
        if ar[i] != i+1:

            #find the value of i+1 from i+1th position
            temp = ar.index(i+1,i+1) 
            
            ar.insert(i,i+1) #insert i+1 in the ith position

            ar.pop(temp+1) #remove the value of i+1 from the right

            c+=1 #every time you do a swap, increment the counter
    print (ar) #if you want to check if ar is correct, use this print stmt
    return c

a = [1,3,4,5,6,7,2,8]

print (minSwap(a))

Общее количество свопов для приведенного выше примера составляет 1. Он просто вставляет 2 на втором месте и выскакивает 2 из позиции 6.

Я запустил код для a = [1,6,5,4,3,8,2,7], и он заменил 5 перемещений.

Я запустил код для a = [1,3,5,4,6,8,2,7], и он поменял местами за 3 хода.

Если вы пытаетесь понять, как это работает, используйте оператор печати сразу после оператора if. Он сообщит вам об заменяемом элементе.

Answer 3

Из вашего кода я понимаю, что сортировка здесь не проблема, так как вы знаете, что в конечном итоге получите ar[i] == i+1. Учитывая это, почему бы не изменить свой блок else, чтобы поменять текущий элемент на его слот, и повторять, пока ar [i] не станет правильным.

    else:
        while ar[i] != i+1:
            temp = ar[i]
            ar[i] = ar[temp - 1]
            ar[temp - 1] = temp