Single Number II

题目

Single Number II
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

解题报告

理解题意

• 给定一个数组，里面的元素均出现了 K(K > 1) 次,出了一个元素出现 P(P>=1 , P % K != 0) 次，让找到这个元素。
  gi

思路

• 首先构建一个计数器，可以实现对 01 数组进行计数，每次遇见1 counter 自增，如果自增至 K，则 counter 重至为 0

  def counter:
      for i in array:
          if i:
              count += 1
          if counter == k:
              count = 0

• 那么什么位操作遇到 0 不变，遇到 1 自增，也就是资深取反（因为自增碰到 1 会变成 0）
• 对于某一位数字 0 或者 1 来讲：
• 碰到 0 不变的操作有两个： x = x | 0 另一个是 x = x ^ 0
• 但异或(XOR)操作明显更加合适: 1 ^ 1 = 0 , 0 ^ 1 = 1, 0 ^ 0 = 0
• 因此对于 counter 来讲， counter = counter ^ 1
• 但题目需要覆盖 K 位，那就是  2 ^ m >= K，因此需要 最少 logk 个
• 因此 m 位从高到低为C[m], C[m-1],... C[1]
• 对于最低位 : C[1] = C[1] ^ i;
• 对于C[2]，只有前一位为 1 的时候才进位，C[2] = C[2] ^ (C[1] & i)
• 对于C[k], 进位条件 i == 1 && C[j] == 1 for all j < k

  def update:
      for i in array:
          C[m] ^= (c[m-1] & c[m-2] & .... C[1] & i)
          ...
          C[2] ^= C[1] & i
          C[1] ^= i
          // 要从最高位开始更新

• 但更新策略还不完整，需要达到阈值的时候变成 0
• 因此需要一个 mask = 0 if counter == k else 1
• 于是每次更新的时候 C[i] & mask
• 假设 k 的二进制形式为 k[m], k[m-1]…k[1]
• 那么 mask = ~(y1 & y2 ... & ym) where yj = cj if kj = 1 else yj = ~ cj
• 这样子的话当c == k时，yj全部等于1，mask值为0，而 c != k时，yj必不全为1，则mask值必为1.

  for i in array:
   	c[m] ^= (c[m-1] & c[m-2] & ... & c[1] & i)
     ...
     c[2] ^= (c[1] & i)
     c[1] ^= i  # 注意要先从高位开始更新
  
     for j in range(m):
       	y[j] = c[j] if k[j] else ~c[j]
     mask = ~(y[1] & y[2] ... & y[m])
  
     for j in range(m):
       	c[m] &= mask
         ...
         c[1] &= mask

代码

c1 = 0
c2 = 0
m = 0
for i in nums:
  	c2 ^= c1 & i
    c1 ^= i
    mask = ~(c1 & c2) # k = 3, 二进制形式为11，则c1和c2都不用取反
    c1 &= mask
    c2 &= mask
return c1 # p = 1, 则最后c1 = single