Given2*n + 1numbers, every numbers occurs twice except one, find it.

Example

Given[1,2,2,1,3,4,3], return4

O(n)的算法

没想出O(n)的算法，于是只好看了下Discuss，发现了一个很有意思的解决方式：利用XOR运算，原文地址:https://oj.leetcode.com/discuss/6170/my-o-n-solution-using-xor

因为A XOR A = 0，且XOR运算是可交换的，于是，对于实例{2,1,4,5,2,4,1}就会有这样的结果：

(2^1^4^5^2^4^1) => ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5

就把只出现了一次的元素(其余元素均出现两次)给找出来了！

算法复杂度为O(n)，且不需要额外空间，代码如下：

class Solution {
public:
    /*
     * @param A: An integer array
     * @return: An integer
     */
    int singleNumber(vector<int> &A) {
        // write your code here
        int sum = 0;
        for (int i = 0; i < A.size(); i++) {
            sum ^= A[i];
        }
        return sum;
    }
};