首页 > 代码库 > 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一个数组中有两个数字ab只出现一次,其他数字都出现了两次。请找出这两个只出现一次的数字?

思路:若将数组中的所以数字进行异或,那么最终结果为 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一个数组中有三个数字abc只出现一次,其他数字都出现了两次。请找出这三个只出现一次的数字?

思路:此处转载自:http://zhedahht.blog.163.com/blog/static/25411174201283084246412/

如果我们把数组中所有数字都异或,那最终的结果(记为x)就是abc三个数字的异或结果(x=a^b^c)。其他出现了两次的数字在异或运算中相互抵消了。

 

我们可以证明异或的结果x不可能是abc三个互不相同的数字中的任何一个。

我们用反证法证明。假设x等于abc中的某一个。比如x等于a,也就是a=a^b^c。因此b^c等于0,即b等于c。这与abc是三个互不相同的三个数相矛盾。

 

由于xabc都各不相同,因此x^ax^bx^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)的结果。由于对于非0nf(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^ax^bx^c的结果中,有一个或者三个数字的第m位是1

我们使用反正法证明不可能三个数字第m位都是1.

如果x^ax^bx^c的第m位都是1,那么abc三个数字的第m位和x的第m位都相反,因此abc三个数字的第m位相同。如果abc三个数字的第m位都

0x=a^b^c结果的第m位是0。由于xa两个数字的第m位都是0x^a结果的第m位应该是0。同理可以证明x^bx^cm位都是0。这与我们的假设矛盾。

如果abc三个数字的第m位都是1x=a^b^c结果的第m位是1。由于xa两个数字的第m位都是1x^a结果的第m位应该是0

同理可以证明x^bx^cm位都是0。这还是与我们的假设矛盾。

因此x^ax^bx^c三个数字中,只有一个数字的第m位是1。于是我们找到了能够区分abc三个数字的标准。

=============================================================

 

这里我们需要注意上面只是在已知a,b,c的情况下的理论证明,具体编程则有些不一样:

我们先求得 x = a ^ b ^ c

我们可以将x分别与数组中的元素再进行一次异或,得到一个新的数组,但是并没有改变数组的特性。

比如与数组中有两个相等的数字d

那么经过处理之后这两个数还是相等的,只不过结果为x ^ d 

 

==============================================================

这样我们可以将数组分成两部分,这里假设a的m位为1。

则两个子数组分别为:sub1:包含a   == Problem 1

                           sub2:包含b, c  == Problem2

 

代码:

 

 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