题目描述：
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?
要完成的函数：
int singleNumber(vector<int>& nums)
说明：
1、给定一组数，这组数中除了有一个元素只出现一次，其他元素都出现了两次，要求输出这个只出现一次的元素的值。
2、时间复杂度O(n)，也就是只能从头到尾遍历一次；空间复杂度O(1)，只能使用常数级的空间。
3、照这道题目的要求来看，既不能常规做法的定义一个数组，记录每个数出现了几次；也不能双重循环找到出现两次的数，然后把它们都删掉，接着继续遍历，直到最后只剩下出现一次的数。所以这道题目要求只能遍历一遍，那就只能从数学上寻找方法了。
4、这道题目笔者本人想了很长时间，都不知道采用什么数学方法好，直到在discuss中看到大神采用异或（XOR）的做法……以下举例说明为什么异或能够处理这道问题。
举例说明：
先说明一点，所有整数在计算机中都采用二进制的表示方法。以下举两个例子：
1、数组为1、1、2，在计算机中表示为0001,0001,0010，那么0001^0001=0000，接着0000^0010=0010。最后得到的结果是2，也就是只出现一次的这个数，2。
2、数组为1、2、1，在计算机中表示为0001,0010,0001，那么0001^0010=0011，接着0011^0001=0010。最后得到的结果是2，也就是只出现一次的这个数，2.
为什么会这样子？
因为异或是两个相同的数则异或结果为0，两个不同的数异或结果为1，并且异或满足交换律和结合律，所以我们可以得到这样的结论：A^B^C^B^D^C^A=D。
异或其实是“记录”了所有出现过的数，只要你第二遍出现，异或结果就会为0，直到一个只出现一次的数，那么异或结果最终为这个只出现一次的数的数值。
这个结论其实我思考了一会，才明白了过来。异或能够记录曾经出现过的数，然后一直在等待第二遍出现，来异或为0。如果一直没有第二遍出现，数组中全都是只出现一遍的数，那么最终结果会是很奇怪的。各位同学不妨试试。
异或就是我想要的那个数学方法。
代码：
int singleNumber(vector<int>& nums)
{
for(int i=1;i<nums.size();i++)
nums[0]^=nums[i];
return nums[0];
}
- 还没有人评论，欢迎说说您的想法！
客服
