136. Одиночное число (Single Number)

Задание.

Получен непустой массив целых чисел nums, каждый элемент появляется дважды, за исключением одного.

Найди этого единственного.

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример 1.

Входные данные: nums = [2,2,1]

Результат: 1

Пример 2.

Входные данные: nums = [4,1,2,1,2]

Результат: 4

Пример 3.

Входные данные: nums = [1]

Результат: 1

Решение.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(auto x: nums) {
            ans ^= x;
        }
        return ans;
    }
};

Способ решения.

Используются свойства операции XOR (исключающее ИЛИ), при котором a XOR a = 0 (число, к которому применяется операция “исключающего ИЛИ” с самим собой, в результате даёт ноль).

Таким образом, если в последовательности все числа встречаются дважды, то итогом применения к ним операции “исключающего ИЛИ” будет ноль, а единственным числом последовательности останется число, которое встерчается единожды.