136. Single Number

136. Single Number
给定一个整数数组，除了一个元素外，每个元素都会出现两次。找到那一个。
[思路]

• 要求线性时间，不用额外空间；
• 搜索别人答案：使用位运算，相同的数有相同的位，使用异或'^'操作则结果为0，通过遍历所有元素进行异或运算，得到剩余的一个数；

    int singleNumber(vector<int>& nums) {
        if(nums.empty()) return 0;
        int first = nums[0];
        for(int i = 1; i<nums.size();i++) {
            first = first ^ nums[i];
        }
        return first;
    }