Come si può eliminare un elemento arbitrario da un array (vettore) in tempo costante, se l'ordine degli elementi non è importante?

Se l'ordine degli elementi in un array (vetore) non è importante, puoi rimuovere un elemento arbitrario in tempo costante sostituendo l'elemento da rimuovere con l'ultimo elemento dell'array e poi riducendo la dimensione dell'array di 1.

Questo evita di spostare tutti gli elementi successivi, cosa che di solito richiede tempo lineare.

Esempio in C++:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // sostituisce l'elemento da rimuovere con l'ultimo
    vec.pop_back();          // rimuove l'ultimo elemento
}