欢迎fork and star：Nowcoder-Repository-github
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?
解析
- Tags Bit Manipulation
我们来论证一下这个算法的正确性：
0 ^ 1 = 1, 1 ^ 0 = 1, 0 ^ 0 = 0, 1 ^ 1 = 0
对于任意整数n，n ^ 0 = n, n ^ n = 0
（1）当n与0异或时，由于0的所有二进制位均为0，因此，n的二进制位中为1的与0相应位的二进制位0异或结果为1，n的二进制位中为0的与0相应位的二进制位0异或结果为0，因此异或后的结果与n本身完全相同；（2）当n与n异或时，由于其二进制位完全相同，而根据1中0 ^ 0 = 0, 1 ^ 1 = 0，n ^ n结果的所有位均为0，所以结果为0。
异或运算满足交换结合律 a ^ b ^ c = a ^ c ^ b.
其实我们可以将所有的abc均看做二进制形式，其结果可以看做是如下运算：
00000000 00000000 00000000 00000010 a = 2
^
00000000 00000000 00000000 00000001 b = 1
^
00000000 00000000 00000000 00000100 c = 4
00000000 00000000 00000000 00000111 result = 7
即所有运算数的每一位分别异或，因此不论运算顺序如何，结果都相同。
// single number
class Solution_136 {
public:
int singleNumber(int A[], int n) {
//思路1：先排序，在相邻比较，时间O(nlogn)
//思路2：异或运算，按二进制的位异或
int ret = 0;
for (unsigned int i = 0; i < n;i++)
{
ret ^= A[i];
}
return ret;
}
};
class Solution {
public:
int singleNumber(vector<int>& nums) {
for(int i=1;i<nums.size();i++)
{
nums[0]^=nums[i];
}
return nums[0];
}
};
延伸
加减法 时间复杂度O(n)，空间复杂度O(c)
算法描述
计算1+2+…+n，用该值减去data中的每个数，差就是缺少的数。
该算法简单易懂，且计算1+2+…+n可直接用公式n*(n+1)/2，然后减去data中的每个数需要遍历data，时间复杂度O(n)，空间复杂度O(c)。
-
当n很大的时候，n*(n+1)/2是有可能溢出的，这种情况下加减法的这种解决方案是有问题的