Hoe kun je een willekeurig element uit een array (vector) verwijderen in constante tijd, als de volgorde van de elementen niet belangrijk is?

Als de volgorde van de elementen in een array (vector) niet belangrijk is, kun je een willekeurig element in constante tijd verwijderen door het te vervangen door het laatste element van de array en vervolgens de grootte van de array met 1 te verminderen.

Dit voorkomt het verschuiven van alle volgende elementen, wat meestal lineaire tijd kost.

Voorbeeld in C++:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // vervangt het te verwijderen element door het laatste
    vec.pop_back();          // verwijdert het laatste element
}