找出数组中只出现一次的数字

[spring011]

一个整型数组 nums 里除一个数字之外，其他数字都出现了两次。请找出这一个只出现一次的数字。

算法分析
所有元素进行异或操作。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 00，不同结果为 11。那么在计算过程中，成对出现的数字的所有位会两两抵消为 00，最终得到的结果就是那个出现了一次的数字。

    function findSingleNumber(arr) {
       let ret = 0
       for (let i = 0; i < arr.length; i++) {
           ret ^= n
       }
       return ret
    }

复杂度分析

• 时间复杂度：O(n)，我们只需要遍历数组一次。
• 空间复杂度：O(1)，只需要常数的空间存放若干变量。