136. 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?

数组中只有一个数只出现一次，其余的数都出现两次，找出出现一次的那个数。采用异或运算来处理。

异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现依次的数字，因为那些出现两次的数字全部在异或中抵消掉了。

代码如下：

 1 class Solution { 2 public: 3     int singleNumber(vector<int>& nums) {    4         int n = 0; 5         for(int i = 0; i < nums.size(); i++) 6         { 7             n ^= nums[i]; 8         } 9         return n;10     }11 };

leetcode 136