Comment peut-on supprimer un élément arbitraire d'un tableau (vecteur) en temps constant, si l'ordre des éléments n'a pas d'importance?

Si l'ordre des éléments dans un tableau (vecteur) n'est pas important, il est possible de supprimer un élément arbitraire en temps constant en remplaçant l'élément à supprimer par le dernier élément du tableau, puis en réduisant la taille du tableau de 1.

Cela évite de décaler tous les éléments suivants, ce qui prend généralement un temps linéaire.

Exemple en C++ :

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // remplace l'élément à supprimer par le dernier
    vec.pop_back();          // supprime le dernier élément
}