136. Single Number题目大意为:
给出一个数组，其中只有一个数字出现了一次，其他数字都出现两次，找出只出现一次的数字。
137. Single Number II题目大意为:
给出一个数组，其中只有一个数字出现了一次，其他数字都出现了三次，找出只出现一次的数字。
260. Single Number III题目大意为:
给出一个数组，其中有两个数字出现了一次，其他出现两次，找出那两个出现一次的数字。
这三道题是一个系列，且非常类似，解题方法都是Bit Manipulation, 所以我把他们放到了一篇博客里。
思路
我们用二进制去考虑，求数组中所有数字二进制每一位上出现1的次数，例如数组为[1, 1, 3, 3, 2](二进制为[01, 01, 11, 11, 10])。将二进制每一位单独相加，结果是（3，4），意为数组中所有的数，在二进制第一位上共出现4个1，在二进制第二位出现3个1。
以136题为例，因为只有一个数字出现一次，其他数字都是两次。所以二进制位数上出现1的次数和，有一些位是偶数，有一些位是奇数，和是奇数的那些位组成的数就是我们要找的只出现一次的数。上例中，将二进制第二位（和为奇数）设为1，其余位（和为偶数）设为0，就得到了结果2.
**推广：如果只有一个数字出现1次，其余数字都是出现N次。对二进制每一位单独求和，将和不是N的倍数的位设为1，其余位为0，得到的数字就是只出现1的数字。**
因为int有32位，我们可以用大小为32的数组保存每一位的和。代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// array[32]
class Solution {
public:
int singleNumber(vector<int>& nums) {
int cnt[32] = {};
int ans = 0;
int N = 2; // 136题其余数字出现2次;如果是137题 N = 2;
for(int i = 0;i < 32;i++)
{
for(int j = 0;j < nums.size();j++)
{
cnt[i] += (nums[j]>>i) & 1;
}
ans |= (cnt[i] % N) << i;
}
return ans;
}
};
更进一步
我们其实并不需要知道每一个二进制位之和具体是多少，只需要知道其对N的余数是0还是1.以137题为例，需要知道的是每一位的和对于3的余数，那么每一位只有3个状态（0, 1, 2），3个状态只需要用2个二进制位就可以表示了。用两个数字表示32位每一位的状态:
1 | int one = 0; |
用one_i表示one第i二进制位的值，(two_i, one_i)表示第i位的状态，3种状态分别为(0, 0), (0, 1), (1, 0).
状态转移如下：
// 遇到0不变
(x, x) + 0 --> (x, x)
// 遇到1
(0, 0) + 1 --> (0, 1) + 1 --> (1, 0) + 1 --> (1, 1) --> (0, 0)
因为看到这并不是一个加法( (1, 0) + 1 --> (0, 0) ), 我列出了真值表，凑出了表达式 >_<…1
2
3
4
5// 表达式右边的two, one代表的都是上一轮的值
// two
two = two ^ (nums[i] & (one ^ two));
// one
one = (nums[i] ^ one) & (~two);
但还是我图样，(1, 0) + 1 --> (0, 0) 可以分为两步: (1, 0) + 1 --> (1, 1) --> (0, 0). 即正常按加法去计算，每轮计算完检查一下，如果为(1, 1)，那么再强行置为(0, 0)。
137题代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// one, two
class Solution {
public:
int singleNumber(vector<int>& nums) {
int n = nums.size();
int one = 0;
int two = 0;
int three = 0;
for(int i = 0;i < n;i++)
{
two |= one & nums[i];
one = one ^ nums[i];
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
};
对于136题，因为是对2取余，所以只有两个状态：（0），（1）。
表达式为异或：
state = state xor nums[i]
应该谨记异或的性质，两个相同的数异或结果为0，任何数异或0还是原值：
x xor x = 0
x xor 0 = x
136题代码:1
2
3
4
5
6
7
8
9class Solution {
public:
int singleNumber(vector<int>& nums) {
int len = nums.size();
for(int i = 1;i < len;i++)
nums[0] ^= nums[i];
return nums[0];
}
};
有两个数出现一次
对于260题，有两个数字出现了一次，其余出现了两次。
这该怎么求解呢？两个数 a, b 混在一起，我们如果用上文的Bit Manipulation的方法，只能求出 a xor b。
不过仔细想想，a xor b代表的就是a, b两个数在哪些二进制位上不同，我们可以根据其中任意一位（就用最右边的不同位）将整个数组分为两部分，a, b分别位于两个不同部分，且那些出现两次的数（两个相同的数）必定都分到同一个部分。
问题转化为，每一部分都有一个出现一次的数，其余数字都出现两次，等同于136题。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> re;
int len = nums.size();
int diff = 0;
for(int i = 0;i < len;i++)
diff ^= nums[i];
// find one bit that can distinguish the two numbers
for(int i = 0;i < 32;i++)
{
if(diff & (1 << i))
{
diff &= (1 << i);
break;
}
}
// devide into two group, one & diff == true, another & diff == false
int ans1 = 0;
int ans2 = 0;
for(int i = 0;i < len;i++)
{
if(nums[i] & diff)
{
ans1 ^= nums[i];
}
else
{
ans2 ^= nums[i];
}
}
re.push_back(ans1);
re.push_back(ans2);
return re;
}
};
GitHub:
136. Single Number
137. Single Number II
260. Single Number III