¿Cómo se puede eliminar un elemento arbitrario de un array (vector) en tiempo constante, si el orden de los elementos no importa?

Si el orden de los elementos en un array (vector) no importa, se puede eliminar un elemento arbitrario en tiempo constante reemplazando el elemento a eliminar por el último elemento del array y luego reduciendo el tamaño del array en 1.

Esto evita desplazar todos los elementos posteriores, lo cual generalmente toma tiempo lineal.

Ejemplo en C++:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // reemplaza el elemento a eliminar por el último
    vec.pop_back();          // elimina el último elemento
}