Каким образом можно осуществить удаление произвольного элемента из массива (вектора) за постоянное время, если порядок элементов не имеет значения?

Если порядок элементов в массиве (векторе) не важен, можно удалить произвольный элемент за постоянное время, заменив удаляемый элемент последним элементом массива и затем уменьшив размер массива на 1.

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

Пример на C++:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // заменяем удаляемый элемент последним
    vec.pop_back();          // удаляем последний элемент
}