Como pode remover um elemento arbitrário de um array (vetor) em tempo constante, se a ordem dos elementos não for importante?

Se a ordem dos elementos num array (vetor) não for importante, pode remover um elemento arbitrário em tempo constante substituindo o elemento a remover pelo último elemento do array e depois reduzindo o tamanho do array em 1.

Isto evita deslocar todos os elementos seguintes, o que normalmente leva tempo linear.

Exemplo em C++:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // substitui o elemento a remover pelo último
    vec.pop_back();          // remove o último elemento
}