Как в Python удалить элемент из списка за O(1)?

Удаление элемента из списка (массива) в Python за константное время O(1) возможно только при условии, что порядок оставшихся элементов не важен.

Алгоритм состоит из двух шагов:

1. Заменить удаляемый элемент последним элементом списка.
2. Удалить последний элемент списка с помощью метода pop().

Операция доступа по индексу (lst[index] = ...) и удаление последнего элемента (lst.pop()) выполняются за O(1), что обеспечивает общую константную сложность.

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

def remove_at_constant_time(items: list, index_to_remove: int):
    """Удаляет элемент по индексу за O(1), нарушая порядок."""
    if not 0 <= index_to_remove < len(items):
        raise IndexError("Index out of range")

    # Заменяем удаляемый элемент последним
    items[index_to_remove] = items[-1]

    # Удаляем последний элемент, что является быстрой операцией
    items.pop()

# Использование
my_list = [10, 20, 30, 40, 50]
# Удаляем элемент с индексом 2 (значение 30)
remove_at_constant_time(my_list, 2)
print(my_list) # Вывод: [10, 20, 50, 40]

Важное замечание: Стандартные методы, такие как list.pop(index) (с указанием индекса) или del list[index], имеют сложность O(n), так как требуют сдвига всех последующих элементов для заполнения образовавшегося "пробела".