136. Single Number

Задача

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

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

Пример 1:

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

Выходные данные: 1

Пример 2:

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

Выходные данные: 4

Пример 3:

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

Выходные данные: 1

Решение

Решение

/**
 * Временная сложность: O(n) - один проход по массиву
 * Пространственная сложность: O(1) - используем только одну переменную
 */
function singleNumber(nums) {
    let result = 0;
 
    // XOR всех элементов: одинаковые пары обнуляются, остается уникальный
    for (let num of nums) {
        result ^= num;
    }
 
    return result;
}
 
console.log(singleNumber([2, 2, 1])); // 1
console.log(singleNumber([4, 1, 2, 1, 2])); // 4
console.log(singleNumber([1])); // 1