LeetCode 136 - Single Number

问题描述：

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

时间复杂度为 O(n) 算法

算法要用到异或运算，异或运算 的规律如下所示：

0 xor 0 = 0

0 xor 1 = 1

1 xor 0 = 1

1 xor 1 = 0

很容易验证一个异或运算的性质：任何一个数字异或它自己都等于0，试想有个数组 $[A, B, A, C, B]$，数字 $A$ 和数字 $B$ 重复出现两次，数字 $C$ 只出现一次，如果我们将数组所有数字进行异或运算，会出现什么情况？首先，可以写出一个表达式
$$
A \text{ xor } B \text{ xor } A \text{ xor } C \text{ xor B}
$$

由于异或运算满足交换律和结合律，因此可以得到下面这个表达式
$$
(A \text{ xor } A ) \text{ xor } ( B \text{ xor } B) \text{ xor C}
$$
由于 $A \text{ xor } A = 0$ 以及 $B \text{ xor } B = 0$，并且0与任何数异或都为原来的数，因此上面的表达式最终化简为
$$
(A \text{ xor } A ) \text{ xor } ( B \text{ xor } B) \text{ xor C} = C
$$
可见，对数组所有数进行异或运算，最终结果就是那个只出现一次的数。知道算法原理，我们可以很容易写出实现代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto it=nums.begin(); it!=nums.end(); ++it)
            ret ^= *it;

        return ret;
    }
};

int main()
{
    Solution solu;

    vector<int> v1 = {2, 3, 2, -1, 3};
    cout << "Single Number is: " << solu.singleNumber(v1) << endl;

    return 0;
}