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?
很经典的面试题，找出数组中唯一一个只出现一次的数。
做法是把所有的数异或起来，因为两个相同的数异或为0，所以数组中两两异或为0，最后就剩下那个只出现过一次的数。时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
int singleNumber(vector<int>& nums) {
if (nums.empty()) return 0;
int ans = 0;
for(int i = 0; i < nums.size(); ++i) {
ans = nums[i] ^ ans;
}
return ans;
}
};
