Wie kann man ein beliebiges Element aus einem Array (Vektor) in konstanter Zeit entfernen, wenn die Reihenfolge der Elemente keine Rolle spielt?

Wenn die Reihenfolge der Elemente im Array (Vektor) nicht wichtig ist, kann man ein beliebiges Element in konstanter Zeit entfernen, indem man das zu entfernende Element durch das letzte Element des Arrays ersetzt und dann die Größe des Arrays um 1 verringert.

Dadurch wird das Verschieben aller nachfolgenden Elemente vermieden, was in der Regel lineare Zeit in Anspruch nimmt.

Beispiel in C++:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // ersetzt das zu entfernende Element durch das letzte
    vec.pop_back();          // entfernt das letzte Element
}