Как удалить элемент из списка со сложностью O(1)

В Python можно удалить элемент из списка за O(1), если не важен порядок элементов. Для этого замените удаляемый элемент последним элементом списка и уменьшите размер списка через pop():

def remove_fast(lst, index):
    lst[index] = lst[-1]  # заменяем удаляемый элемент последним
    lst.pop()  # удаляем последний элемент (O(1))

Пример использования:

numbers = [1, 2, 3, 4, 5]
remove_fast(numbers, 1)  # удаляем элемент с индексом 1
print(numbers)  # [1, 5, 3, 4]

Важно: этот метод нарушает порядок элементов. Для сохранения порядка потребуется O(n) из-за необходимости сдвигать элементы.