Jak lze odstranit libovolný prvek z pole (vektoru) v konstantním čase, pokud na pořadí prvků nezáleží?

Pokud pořadí prvků v poli (vektoru) není důležité, lze libovolný prvek odstranit v konstantním čase tím, že jej nahradíme posledním prvkem pole a poté zmenšíme velikost pole o 1.

Tím se zabrání posunu všech následujících prvků, což obvykle zabere lineární čas.

Příklad v C++:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // nahradí odstraňovaný prvek posledním
    vec.pop_back();          // odstraní poslední prvek
}