136-只出现一次的数字

题目

给定一个非空整数数组，除了某个元素只出现一次意外，其余每个元素均出现两次。找出那个只出现一次的元素。
要求：

1. 算法应该具有线性时间复杂度
2. 不可以使用额外空间来实现

示例

输入：[2,2,1]
输出： 1

代码实现

function  singleNumber(nums) {
    for (let index = 1; index < nums.length; index++) {
        nums[0] = nums[0] ^ nums[index];
    }
    return nums[0];
}

思路解析

1. 题目要求线性时间复杂度，即O(n),不适用额外的空间，那就只能在数组本身身上进行操作。
2. 这里要用的异或操作：两个相等的数异或为0，一个不为0的数与0异或为这个数本身。 也就是 1 ^ 1 = 0 ; 1 ^ 0 = 1; 2 ^ 2 ^ 1 = 1;