Rechercher un entier ne se produisant pas deux fois dans un tableau

J’essaie de résoudre ce problème: dans un tableau entier, tous les nombres apparaissent exactement deux fois, à l’exception d’un nombre unique qui apparaît exactement une fois.

Une solution simple consiste à sortinger le tableau, puis à tester la non-répétition. Mais je cherche une meilleure solution qui a une complexité temporelle de O (n).

Vous pouvez utiliser l’opération “xor” sur tout le tableau. Chaque paire de numéros s’annulera, vous laissant avec la valeur recherchée.

int get_orphan(int const * a, int len) { int value = 0; for (int i = 0; i < len; ++i) value ^= a[i]; // `value` now contains the number that occurred odd number of times. // Retrieve its index in the array. for (int i = 0; i < len; ++i) { if (a[i] == value) return i; } return -1; }