Jak można usunąć dowolny element z tablicy (wektora) w czasie stałym, jeśli kolejność elementów nie ma znaczenia?

Jeśli kolejność elementów w tablicy (wektorze) nie jest ważna, można usunąć dowolny element w czasie stałym, zamieniając usuwany element na ostatni element tablicy, a następnie zmniejszając rozmiar tablicy o 1.

Pozwala to uniknąć przesuwania wszystkich kolejnych elementów, co zwykle zajmuje czas liniowy.

Przykład w C++:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // zamienia usuwany element na ostatni
    vec.pop_back();          // usuwa ostatni element
}