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?
题目链接在这里。
这是一道很有意思的题目，大意是说在一个整型数组中，所有的数字都出现了两次，只有一个数是例外，找出这个数。
乍一看感觉很简单啊，开个数组计数就好了~可惜题目还要求要在不使用额外空间的情况下找到解，这就有点蛋疼了…如果使用二分查找倒是不会用到额外空间，可是时间复杂度为O(nlogn)，又不符合题目要求的线性复杂度…
该怎么办呢？该怎么办呢？
其实这个题目的解法非常的巧妙，也非常简单，主要用到了异或运算的性质：
|
1 2 3 |
a xor a = 0 0 xor a = a a xor b = b xor a |
非常非常简单…使用上面的性质可以很容易知道，把数组中所有的数异或起来，得到的结果就是仅出现了一次的数！！！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int singleNumber(int A[], int n) { int ans = 0; for (int i = 0; i < n; ++i) { ans ^= A[i]; } return ans; } }; |