Ako lahko odstranite poljuben element iz poľa (vektorja) v času, ki je odvisen le od velikosti, če vrstni red elementov ni pomemben?

Ak poradie prvkov v poli (vektore) nie je dôležité, môžete odstrániť ľubovoľný prvok v konštantnom čase tak, že ho nahradíte posledným prvkom poľa a potom zmenšíte veľkosť poľa o 1.

Toto zabraňuje posunu všetkých nasledujúcich prvkov, čo zvyčajne trvá lineárny čas.

Prí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ý prvok posledným
    vec.pop_back();          // odstráni posledný prvok
}