Алгоритмическая задача. Ускорить алгоритм

Ты СОРТИРУЕШЬ список. А надо считать кол-во перестановок БЕЗ сортировки. И делается это за один проход по массиву:

 input() # значение N не требуется, но вводить приходится

a = input().split()

b = {v: i for i, v in enumerate(input().split())}

cnt, mx = 0, 0

for v in a:

  if b[v] < mx: cnt += 1

  else: mx = b[v]

print(cnt) 

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

P.S. Наконец-то эта задача появилась на "Ответах" в нормальной формулировке - без дебильных упоминаний начальника с не так вставшими пронумерованными подчинёнными или лейтенанта с пронумерованными же солдатами.

Чувак... Тебе не надо двигать списки. Тебе надо вычислить количество сдвигов. Делай только то, что надо, и с быстродействием все будет хорошо.

Для оптимизации операций со списками можно использовать структуру данных, которая позволяет быстро находить и удалять элементы. В Python для этого подходят библиотеки, активно использующие C/C++ реализацию для увеличения производительности, например, библиотека blist.

Этот подход может позволить ускорить операцию вставки и удаление элемента до O(log N). В решении все еще остается проход по списку, но он выполняется за O(N), так что общая сложность алгоритма становится O(N log N), что может быть достаточно для вашего ограничения в 1 секунду при N до 10^5.

Попробуйте применить следующий код с использованием blist:

 from blist import blist 

 

def min_operations(a, b): 

    a_dict = {num: index for index, num in enumerate(a)} 

    a = blist(a) 

    commands = 0 

    for bi in b: 

        ai = a_dict[bi] 

        a.remove(ai) 

        a.add(bi, i) 

        commands += 1 

    return commands 

 

Пожалуйста, учтите что это предложение основано на теоретической оценке производительности. Фактическая производительность может отличаться и зависеть от многих факторов, включая конкретное оборудование и версию Python. Если этот подход не достигает нужной производительности, то, возможно, вам стоит рассмотреть использование более низкоуровневых языков программирования, таких как C или C++.

Для решения данной задачи можно использовать следующий алгоритм:

1. Создать словарь, где ключами будут элементы списка A, а значениями - их индексы в списке.
2. Создать переменную, которая будет хранить количество операций сдвига.
3. Пройти по списку B и для каждого элемента проверить, находится ли он на своем месте в списке A.
4. Если элемент не на своем месте, то найти его индекс в списке A и вычислить, на сколько позиций его нужно сдвинуть, чтобы он оказался на своем месте.
5. Если индекс элемента в списке B меньше, чем его индекс в списке A, то сдвигать его нужно влево, иначе - вправо.
6. Выполнить сдвиг элемента и увеличить счетчик операций.
7. Повторять шаги 3-6 до тех пор, пока все элементы списка B не окажутся на своих местах в списке A.

Пример реализации на Python:

 def min_shifts(n, a, b): 

    a_dict = {num: index for index, num in enumerate(a)} 

    shifts = 0 

     

    for i in range(n): 

        right_elem = b[i] 

        if a[i] != right_elem: 

            right_elem_index = a_dict[right_elem] 

            diff = right_elem_index - i 

            if diff < 0: 

                diff += n 

            if diff