[算法] 举一反三之n重复数组中找唯一m重复异类数

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;

因而这个状态变化过程可描述为:

  1. 两位二进制数的低位a,在高位b为0时,进行二态变化;在高位b为1时,归0;
  2. 两位二进制数的高位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)

这就是标准的两位二进制数加法,状态变化过程可描述为:

  1. 两位二进制数的低位a,正常进行二态变化;
  2. 两位二进制数的高位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)

状态变化过程可描述为:

  1. 三位二进制数的低位a,在高位c为0时,进行二态变化;在高位c为1时,归0;
  2. 三位二进制数的中位b,在高位c为0时,低位a进位的时候进位二态变化;在高位c为1时,归0;
  3. 三位二进制数的高位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
上一篇:Spring框架整合Struts2框架的传统方法


下一篇:ssh整合思想初步 struts2与Spring的整合 struts2-spring-plugin-2.3.4.1.jar下载地址 自动加载Spring中的XML配置文件 Struts2下载地址