n重复数组,是指数组中的数字都出现n次;
唯一m重复异类数,是指存在唯一一个没出现n次,只出现了m次的数;
这里我简记它为nX+my问题,求解y,其中m < n,数组中都是整数;
3X+y问题
一直没有精力刷leetcode,今天查问题无意中看到了leetcode 137:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次;找出那个只出现了一次的元素。要求时间复杂度O(n),空间复杂度O(1);
没有在第一时间想到思路,于是花时间研究了一下;
这是一个3X+y的问题;先给出最优解:
a, b = 0, 0
for num in nums:
a = (a ^ num) & ~b
b = (b ^ num) & ~a
return a
在2X+y问题中,方法是使用异或操作一遍全数组,最终结果就是那个异类数,但从未深入想过为什么异或会对2X+y问题有效,因而也就无法想通为什么直接异或会对3X+y问题无效;
再看一遍异或的特点:
0 ^ 0 = 0
1 ^ 0 = 1
0 ^ 1 = 1
1 ^ 1 = 0
仔细看看,这是因为异或可以让一个信息位(前面的那个1bit数),在接收到有效信息量(后面的那个1bit数,值为1时为有效)的时候,产生二态变化;
因而如果要解决3X+y问题,就需要有一个可以产生三态变化的操作符,单纯的异或是肯定不行的,因为要对一个信息位保存三种状态,至少需要两个信息位,因而在原本的数字变量空间上操作是不够的;
假定这个三态异或操作用符号^3表示;然后用两个信息位(b, a)保存状态,于是三态异或在接收到有效信息量(1)时的运算特点如下(接收到无效信息量0时不产生变化):
(0, 0) ^3 1 = (0, 1)
(0, 1) ^3 1 = (1, 0)
(1, 0) ^3 1 = (0, 0)
这个三态变化过程,其实是正常的两位二进制数进位加法的一个修改,修改处在于,对于二进制10,再加1时,直接跳过11回到00;
因而这个状态变化过程可描述为:
- 两位二进制数的低位a,在高位b为0时,进行二态变化;在高位b为1时,归0;
- 两位二进制数的高位b,在低位a归0时,进行二态变化;在低位a变为1时,保持为0;
可见a与b的变化规律相似,都要求对方为0时自己进行二态变化,对方为1时自己为0,于是上面的最优解的计算过程就很容易写出来了:
a = (a ^ num) & ~b
b = (b ^ num) & ~a
3X+2y问题
等等,为什么是return a,而不是return b呢?
首先,上面这段代码里的a、b各是一个数字,它位的每个二进制位组合起来,保存了对整个数组^3操作过程中每个二进制位的状态变化;
因为这个^3操作过程中,低位a在第一状态有效,因而要求3X+y问题,需要return a;
因而,如果题目改为:给定一个非空整数数组,除了某个元素只出现两次以外,其余每个元素均出现了三次;找出那个只出现了两次的元素。
求解这个3X+2y问题,答案也就出来了,计算过程同上,而因为高位b在第二状态有效,因而return b即可;
4X+2y问题
再发散思维,改题目:给定一个非空整数数组,除了某个元素只出现两次以外,其余每个元素均出现了四次;找出那个只出现了两次的元素。
沿着上面的思路,需要做一个四态异或操作符^4,同样需要两个信息位进行状态存储,它对于有效信息(1)的运算特点如下:
(0, 0) ^4 1 = (0, 1)
(0, 1) ^4 1 = (1, 0)
(1, 0) ^4 1 = (1, 1)
(1, 1) ^4 1 = (0, 0)
这就是标准的两位二进制数加法,状态变化过程可描述为:
- 两位二进制数的低位a,正常进行二态变化;
- 两位二进制数的高位b,在低位a进位的时候进位二态变化;
于是计算过程可写为:
old_a = a
a = (a ^ num)
b = b ^ ((old_a ^ a) & ~a)
其中(old_a ^ a) & ~a,意义为a由1变为0;
由于这个b的计算核心算子是异或,异或与否合用有危险,不把(old_a ^ a)引进来会出现bug;
因为要求的y出现2次,所以需要找第二状态时的有效位,return b;
4X+3y问题
状态数同时为4,计算过程同4X+2y,返回时找第三状态时的有效位,因而也return b;
5X+4y问题
题目修改为:给定一个非空整数数组,除了某个元素只出现4次以外,其余每个元素均出现了5次;找出那个只出现了4次的元素。
状态数上升到5,需要做一个五态异或操作符^5,需要3个信息位(c, b, a)做状态存储,对有效信息(1)的运算特点如下:
(0, 0, 0) ^5 1 = (0, 0, 1)
(0, 0, 1) ^5 1 = (0, 1, 0)
(0, 1, 0) ^5 1 = (0, 1, 1)
(0, 1, 1) ^5 1 = (1, 0, 0)
(1, 0, 0) ^5 1 = (0, 0, 0)
状态变化过程可描述为:
- 三位二进制数的低位a,在高位c为0时,进行二态变化;在高位c为1时,归0;
- 三位二进制数的中位b,在高位c为0时,低位a进位的时候进位二态变化;在高位c为1时,归0;
- 三位二进制数的高位c,在低位a和中位b同时归0时,进行二态变化;
计算过程可写为:
old_a = a
a = (a ^ num) & ~c
b = (b ^ ((old_a ^ a) & ~a)) & ~c
c = (c ^ num) & ~b & ~a
由于y出现的次数是4,高位c在状态4时有效,因而返回c;
-----------------------------
测试代码:
def X3_y1(nums):
a, b = 0, 0
for num in nums:
a = (a ^ num) & ~b
b = (b ^ num) & ~a
return a def X3_y2(nums):
a, b = 0, 0
for num in nums:
a = (a ^ num) & ~b
b = (b ^ num) & ~a
return b def X4_y2(nums):
a, b = 0, 0
for num in nums:
old_a = a
a = (a ^ num)
b = b ^ ((old_a ^ a) & ~a)
return b def X4_y3(nums):
return X4_y2(nums) def X5_y4(nums):
a, b, c = 0, 0, 0
for num in nums:
old_a = a
a = (a ^ num) & ~c
b = (b ^ ((old_a ^ a) & ~a)) & ~c
c = (c ^ num) & ~b & ~a
return c print (X3_y1([2, 3, 2, 2])) # 3
print (X3_y2([2, 3, 2, 3, 2])) # 3 print (X4_y2([2, 2, 3, 2, 3, 2])) # 3
print (X4_y3([2, 2, 3, 2, 3, 3, 4, 3, 4, 4, 2])) #4
print (X4_y3([5, 5, 8, 5, 8, 8, 5])) # 8 print (X5_y4([5, 5, 8, 5, 8, 8, 5, 8, 5])) # 8
执行结果:
3
3
3
4
8
8