136. Single Number

题目描述：给一个整数数组，其中除了一个元素外每个元素都出现两次，找出这个只出现一次的元素。要求时间复杂度O(n)，空间O(1)。

分析：设一个数组记录每个数的出现次数如 c[nums[i]] ++，可满足线性的时间复杂度，但是空间为O(n)。或者可以先排序，在遍历一遍，若出现nums[i] != nums[i + 1] 则找到了，但是时间复杂度O(nlgn)。利用位运算的性质：

1. 一个数异或另一个数偶数次还是原数。

2. 任何数与0异或还是原数。

3. 任何数与1异或是其相反数。

代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int x = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            x ^= nums[i];
        }
        return x;
    }
};