首页 > 代码库 > LeetCode之Single Number以及拓展
LeetCode之Single Number以及拓展
Problem 1：一个数组中有一个数字a只出现一次，其他数字都出现了两次。请找出这个只出现一次的数字？
考察知识点：异或运算
思路：比如数字 b^b = 0
a^0 = a
因此，可以将数组中的所有数字进行异或，而最终异或的结果即为所求只出现一次的数字a.
代码：
1 def SingleNumber1(Array):
2 ret = 0
3 for i in Array:
4 ret ^= i
5 return ret
==========================================================
Problem 2：一个数组中有一个数字a只出现一次，其他数字都出现了三次。请找出这个只出现一次的数字？
考察知识点：位运算
解法一：
考虑用统计的思路来解这道题，如果一个数出现了三次就消掉，int的32个位都是由0/1组成的，所以将所有数的对应位加起来，
再将各位的统计和对3取模，最终剩下的结果就是要找出的数。
例如：数组 [4 7 4 4](这里为了方便，我们取int的最后四位)
4 0 1 0 0
7 0 1 1 1
4 0 1 0 0
4 0 1 0 0
Sum 0 4 1 1
Sum%3 0 1 1 1
最后Sum%3得到的结果0111即7，就是我们所要求的Single Number
代码：
1 def SingleNumber2_1(Array):
2 ret = 0
3 for i in range(0,32):
4 c = 0
5 d = 1 << i
6 for j in range(0, len(Array)):
7 if Array[j] & d:
8 c += 1
9 if c % 3:
10 ret |= d;
11 return ret
解法二：
考虑每一位的统计值，如果累加到3就归为0，则只会有0/1/2三种情况，所以将大小为32的int数组改为只用两个int即可。
第一个int的第i位为0/1代表第i位当前累加有0/1个 1 ，第二个int的第i位为1代表第i位当前累加有2。
当int1和int2中的第i位均为1时，我们将他们都清零。
例如：数组 [4 7 4 4](这里为了方便，我们取int的最后四位)
4 0 1 0 0
one 0 1 0 0
two 0 0 0 0
=====================
7 0 1 1 1
one 0 0 1 1
two 0 1 0 0
=====================
4 0 1 0 0
one 0 0 0 0
two 0 0 1 1
=====================
4 0 1 0 0
one 0 1 0 0
two 0 0 0 0
=====================
代码：
1 def SingleNumber2_2(Array): 2 one = 0 3 two = 0 4 three = 0 5 for i in range(0, len(Array)): 6 two |= (one & Array[i]) 7 one ^= Array[i] 8 three = one & two 9 two -= three 10 one -= three 11 return one
==========================================================
Problem 3：一个数组中有两个数字a、b只出现一次，其他数字都出现了两次。请找出这两个只出现一次的数字？
思路：若将数组中的所以数字进行异或，那么最终结果为 a ^ b
由于a != b，可以知道a ^ b != 0.即结果肯定有一位为1.
根据那一位，我们知道a，b的那一位肯定一个是0，一个是1.
我们找到为1的那一位i，根据i位为0/1将数组分成两组，即可将a, b分开。
因此，我们要解决的是两个Problem 1.
代码：
1 def SingleNumber3(Array):
2 ret = 0
3 for i in range(0,len(Array)):
4 ret ^= Array[i]
5 pos = 0
6 for j in range(0,32):
7 if (ret>>j) & 1:
8 pos = j
9 break
10 sub1,sub2 = split(Array,pos)
11 single1 = SingleNumber1(sub1)
12 single2 = SingleNumber1(sub2)
13 return single1,single2
14
15 def split(Array, pos):
16 sub1 = []
17 sub2 = []
18 for i in range(0,len(Array)):
19 if (Array[i]>>pos) & 1:
20 sub1.append(Array[i])
21 else:
22 sub2.append(Array[i])
23 return sub1,sub2 1 def SingleNumber3(Array):
2 ret = 0
3 for i in range(0,len(Array)):
4 ret ^= Array[i]
5 pos = 0
6 for j in range(0,32):
7 if (ret>>i) & 1:
8 pos = i
9 break
10 sub1,sub2 = split(Array,pos)
11 single1 = SingleNumber1(sub1)
12 single2 = SingleNumber1(sub2)
13 return single1,single2
14
15 def split(Array, pos):
16 sub1 = []
17 sub2 = []
18 for i in range(0,len(Array)):
19 if (Array[i]>>pos) & 1:
20 sub1.append(Array[i])
21 else:
22 sub2.append(Array[i])
23 return sub1,sub2
==========================================================
Problem 4：一个数组中有一个数字a只出现一次，其他数字都出现了K次。请找出这个只出现一次的数字？
考察知识点：位运算 and 分情况解决
① K % 2 == 0
基本思路类似于Problem 1
② K % 2 == 1
基本思路类似于Problem 2
代码：
1 def SingleNumber4(Array, k):
2 if k % 2 == 0:
3 ret = SingleNumber1(Array)
4 else:
5 ret = SingleNumber2_2(Array)
6 return ret
==========================================================
Problem 5：一个数组中有三个数字a、b、c只出现一次，其他数字都出现了两次。请找出这三个只出现一次的数字？
思路：此处转载自：http://zhedahht.blog.163.com/blog/static/25411174201283084246412/
如果我们把数组中所有数字都异或，那最终的结果（记为x）就是a、b、c三个数字的异或结果（x=a^b^c）。其他出现了两次的数字在异或运算中相互抵消了。
我们可以证明异或的结果x不可能是a、b、c三个互不相同的数字中的任何一个。
我们用反证法证明。假设x等于a、b、c中的某一个。比如x等于a，也就是a=a^b^c。因此b^c等于0，即b等于c。这与a、b、c是三个互不相同的三个数相矛盾。
由于x与a、b、c都各不相同，因此x^a、x^b、x^c都不等于0。
我们定义一个函数f(n)，它的结果是保留数字n的二进制表示中的最后一位1，而把其他所有位都变成0。比如十进制6表示成二进制是0110，
因此f(6)的结果为2（二进制为0010）。f(x^a)、f(x^b)、f(x^c)的结果均不等于0。
接着我们考虑f(x^a)^f(x^b)^f(x^c)的结果。由于对于非0的n，f(n)的结果的二进制表示中只有一个数位是1，因此f(x^a)^f(x^b)^f(x^c)的结果肯定不为0。
于是f(x^a)^f(x^b)^f(x^c)的结果的二进制中至少有一位是1。假设最后一位是1的位是第m位。那么x^a、x^b、x^c的结果中，有一个或者三个数字的第m位是1。
我们使用反正法证明不可能三个数字第m位都是1.
如果x^a、x^b、x^c的第m位都是1，那么a、b、c三个数字的第m位和x的第m位都相反，因此a、b、c三个数字的第m位相同。如果a、b、c三个数字的第m位都
是0，x=a^b^c结果的第m位是0。由于x和a两个数字的第m位都是0，x^a结果的第m位应该是0。同理可以证明x^b、x^c第m位都是0。这与我们的假设矛盾。
如果a、b、c三个数字的第m位都是1，x=a^b^c结果的第m位是1。由于x和a两个数字的第m位都是1，x^a结果的第m位应该是0。
同理可以证明x^b、x^c第m位都是0。这还是与我们的假设矛盾。
因此x^a、x^b、x^c三个数字中，只有一个数字的第m位是1。于是我们找到了能够区分a、b、c三个数字的标准。
=============================================================
这里我们需要注意上面只是在已知ａ，ｂ，ｃ的情况下的理论证明，具体编程则有些不一样：
我们先求得 x = a ^ b ^ c
我们可以将x分别与数组中的元素再进行一次异或，得到一个新的数组，但是并没有改变数组的特性。
比如与数组中有两个相等的数字d
那么经过处理之后这两个数还是相等的，只不过结果为x ^ d
==============================================================
这样我们可以将数组分成两部分，这里假设a的m位为1。
则两个子数组分别为：sub1：包含a == Problem 1
sub2：包含b, c == Problem２
代码：
1 def SingleNumber5(Array): 2 x = 0 3 for i in range(0,len(Array)): 4 x ^= Array[i] 5 newArray = [] 6 for j in range(0,len(Array)): 7 newArray.append(x^Array[j]) 8 lastOneArrary = func(newArray) 9 ret = 0 10 for i in range(0,len(lastOneArrary)): 11 ret ^= lastOneArrary[i] 12 pos = 0 13 for j in range(0,32): 14 if (ret>>j) & 1: 15 pos = j 16 break 17 sub1, sub2 = split(Array,pos) 18 print(sub1) 19 print(sub2) 20 if len(sub1)%2: 21 single1 = SingleNumber1(sub1) 22 single2, single3 = SingleNumber3(sub2) 23 else: 24 single1 = SingleNumber1(sub2) 25 single2, single3 = SingleNumber3(sub1) 26 return single1, single2, single3 27 28 29 30 def func(Array): 31 newArray = [] 32 for i in range(0,len(Array)): 33 pos = 0 34 for j in range(0,32): 35 if (Array[i]>>j) & 1: 36 pos = j 37 break 38 newArray.append(1<<pos) 39 return newArray