136. 只出现一次的数字

思路

题目要求线性复杂度和不使用额外空间来实现。这就不能使用常规方法来实现，利用异或的特性来实现。

异或运算规则是“同为0，异为1”，即 1⊕1 = 0，0⊕0=0，1⊕0=1，0⊕1=1。

将一个十进制数进行异或运算，会发现如下特性：

1. 一个数与 0 异或等于他本身；
2. 一个数与它本身异或等于0；
3. 异或运算符合交换律和结合律。

例子：

// 特性1
18 ==二进制==> 10010
⊕
0  ==二进制==> 00000
--------------------
18 ==二进制==> 10010

// 特性2
18 ==二进制==> 10010
⊕
18 ==二进制==> 10010
--------------------
0  ==二进制==> 00000

回到题目，题目中提到数组中除一个数出现一次以外，其他数都出现了两次。这道题目就可以利用异或运算特性来做，把数组中的数依次异或运算，出现两次的数异或运算为0，最终结果为出现一次的数。

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

代码

php

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $result = 0;
        for($i = 0; $i < count($nums); $i++) {
            $result ^= $nums[$i];
        }

        return $result;
    }
}

golang

func singleNumber(nums []int) int {
    ans := 0
    for i := 0; i < len(nums); i++ {
        ans = ans ^ nums[i]
    }

    return ans
}