Найти целое число, не встречающееся дважды в массиве

Question

Я пытаюсь решить эту проблему: В целочисленном массиве все числа встречаются ровно в два раза, за исключением одного числа, которое встречается ровно один раз.

Простым решением является сортировка массива, а затем проверка на отсутствие повторения. Но я ищу лучшее решение, имеющее временную сложность O (n).

Answer 1

Вы можете использовать операцию «xor» для всего массива. Каждая пара чисел будет отменять друг друга, оставив вам искомое значение.

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; 
}