Kaip galima atlikti bet kurio elemento pašalinimą iš masyvo (vektoriaus) per pastovų laiką, jei elementų tvarka nėra svarbi?

Jei masyvo (vektoriaus) elementų tvarka nėra svarbi, galima bet kurį elementą pašalinti pastoviu laiku, jį pakeičiant paskutiniu masyvo elementu ir sumažinant masyvo dydį 1.

Tai išvengia visų vėlesnių elementų perkėlimo, kas paprastai užtrunka linijinį laiką.

Pavyzdys C++:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // pakeičia pašalinamą elementą paskutiniu
    vec.pop_back();          // pašalina paskutinį elementą
}