找出 3 次中只出现 1 次的数

March 13, 2019

找出偶数次中只出现一次的数 的进阶版:

给定一个非空整数数组,除了某个元素只出现 11 次以外,其余每个元素均出现 33 次。找出那个只出现了 11 次的元素。

整数以模 33 加法为二元运算的 33 阶循环群 —— Z3\mathbb{Z_3},其中任何数 a{0,1,2}a \in \{0,1,2\} 都满足:

aaa=ea \circ a \circ a = e

它刚好有我们想要的性质。

使用 33 进制表示数,从单位元 00 开始不断进行 33 进制上的“异或运算”(对每个 trit 位执行模 33 加法),最终得到的结果就是那个只出现了一次的数。

模拟 33 进制

AA, BB 两个位序列(也就是两个数),最初都设为 00,某位上分别是 aabb,当这个位:

  • 遇到 00 时,aa, bb 保持不变;

  • 遇到第一次 11 时,aa 变为 11;第二次时,aa00bb11,第三次时复位,即 aa , bb 都变为 00

即如下变化关系(其中 ba{00,01,10}ba \in \{00,01,10\}):

0010111010000 \xrightarrow{1} 01 \xrightarrow{1} 10 \xrightarrow{1} 00

00000 , 01001 , 1001000 \xrightarrow{0} 00 ~,~ 01 \xrightarrow{0} 01 ~,~ 10 \xrightarrow{0} 10

如上 0011 分别对应 bababa \rightarrow ba 上的一个映射(分别记为 f0f_0f1f_1),如下关系成立:

  1. f0=idf_0 = id

  2. f1f1f1=f0f_1\circ f_1 \circ f_1 = f_0

可见 {f0,f1,f12}\{f_0, f_1, f_1^2\} 构成了一个三阶循环群,同构于 Z3\mathbb{Z_3}.

baba 依次输入序列 i1,i2,...,ini_1, i_2, ..., i_n,由循环群的性质可得(#1\#1 是此序列中 11 的个数):

(fin...fi2fi1)(ba)=f1(#1mod3)(ba)(f_{i_n} \circ ... \circ f_{i_2} \circ f_{i_1})(ba) = f_1^{(\#1\mod3)}(ba)

baba 最初设为 0000。满足题目条件的输入序列只有如下两种情况:

  1. 3n+13n+1003m3m11;最终为 id(00)=00id(00) = 00

  2. 3n3n003m+13m+111;最终为 f1(00)=01f_1(00) = 01

两种情况下,aa 位都会和那个“落单”的位一致。

注:如果题目改为 “除了某个元素只出现 22 次以外,其余每个元素均出现 33 次”,那么出现两种情况:3n+23n+2003m3m11,或者 3n3n003m+23m+211:两种情况下 bb 都会和那个出现 22 次的位一致。

映射的实现

baba 变为 bab'a' 的实现如下,其中 xx 表达输入的位,

a=(x+a)(1b)a' = (x + a) * (1 - b)

b=(x+b)(1a)b' = (x + b) * (1 - a')

即位运算:

a' = (x ^ a) & (^b)
b' = (x ^ b) & (^a')

代码为

function singleNumber(nums){
  let a = 0;
  let b = 0;
  for (const x of nums) {
    a = (x ^ a) & (~b);
    b = (x ^ b) & (~a);
  }
  return a;
}

找出 55 次中出现 11 次的数

仿照上面的构造方式,dcba{0000,0001,0010,0100,1000}dcba \in \{0000, 0001, 0010, 0100, 1000\}

000010001100101010011000100000000 \xrightarrow{1} 0001 \xrightarrow{1} 0010 \xrightarrow{1} 0100 \xrightarrow{1} 1000 \xrightarrow{1} 0000

000000000 , 000100001 , 001000010 , 010000100 , 1000010000000 \xrightarrow{0} 0000 ~,~ 0001 \xrightarrow{0} 0001 ~,~ 0010 \xrightarrow{0} 0010 ~,~ 0100 \xrightarrow{0} 0100 ~,~ 1000 \xrightarrow{0} 1000

计算实现如下:

a=(x+a)(1b)(1c)(1d)a' = (x + a) * (1 - b) * (1 - c) * (1 - d)

b=(x+b)(1a)(1c)(1d)b' = (x + b) * (1 - a') * (1 - c) * (1 - d)

c=(x+c)(1a)(1b)(1d)c' = (x + c) * (1 - a') * (1 - b') * (1 - d)

d=(x+d)(1a)(1b)(1c)d' = (x + d) * (1 - a') * (1 - b') * (1 - c')

体会这种实现的精巧之处:

遇到第一个 x=1x=1 时,aa' 变为 11,像“上锁”一样,使得余下三次计算中包含的 (1a)(1-a')00。第二次遇到 x=1x=1 时,aa' 由于 (x+a)=0(x + a) = 0 变为 00bb' 右边的 (1a)(1-a') “锁”打开,bb' 变为 11c,dc',d' 转变为被 b=1b'=1 “锁住”。

当遇到 x=0x=0 时,如果此时状态为 00000000,那么四次计算都会由于左边 (0+0)(0+0) 仍然保持 00;如果此时有一个 11,比如 00100010bb 处在 11 状态),那么 bb “上面”的计算仍然由于左边 (0+0)(0+0)00,而 bb(1+0)(1+0)11,其他位全为 00 使得右边项都为 11bb 仍然为 11

找出 MM 次中出现 kk 次的数

进一步抽象得到下面的通用算法:

nums 中只有一个数是 k(1kM)k(1 \leq k \le M) 次,其他数都出现 MM 次,返回那个出现 kk 次的数

function findkInM(nums, M, k) {
  const record = new Array(M - 1).fill(0);
  for (const x of nums) {
    for (let i = 0; i < M - 1; i++) {
      let recordI = (~0);
      for (let j = 0; j < M - 1; j++) {
        recordI &= (i === j ? (x ^ record[j]) : (~record[j]))
      }
      record[i] = recordI;
    }
  }
  return record[k - 1];
}

时间复杂度为 O(nums.lengthM2)O(nums.length * M^2),空间复杂度为 O(M)O(M)