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?

tag: hash table, bit manipulation

异或有一个很神奇的属性，可以把奇数个元素挑出来。本质是因为：
1. 异或具有交换性 A^B = B^A
2. 0与一个数异或等于它本身

所以该数列中，可以看成把出现两次的元素交换在临近位置，异或之后为0，最后剩下0与出现一次的元素异或，为该元素本身。

一次AC。

class Solution {
public:
    int singleNumber(int A[], int n) {
        if(n == 1){
            return A[0];
        }
        for(int i = 1; i < n; i++){
                A[i] = A[i] ^ A[i-1];
        }
        return A[n - 1];
    }
};