leetcode-137. 只出现一次的数字 II

[francecil]

原题链接：只出现一次的数字 II

给定一个非空整数数组，仅有一个元素出现一次，其余元素都出现三次，求出现一次的元素是哪个

要求 O(n) 时间复杂度，不使用额外空间

[francecil]

分析

只出现一次的数字 这题，是其余元素出现2次，因此我们通过 同一数字异或结果为0、任一数字与0异或等于自身 的结论，对所有元素异或即可得出出现一次的数字

var singleNumber = function(nums) {
  return nums.reduce((pre,cur)=>pre^cur)  
};

本题是三个相同数字,怎么实现 三个相同数字运算结果为0 是关键。

思路1：三进制按位累加

其实只要知道异或的原理，对其进行模拟即可得出结果

对于2个二进制元素，将两个元素的每一位进行相加，并舍弃每次的进位，最后的结果即异或值

同理，累加三个相同三进制数字的每一位，并舍弃每次的进位，最后结果为0

举例 02 02 10 02，设三进制按位加 的运算定位 $

02 $ 02 = 01
01 $ 10 = 11
11 $ 02 = 10

得到最后结果 10

那代码应该怎么写呢？

借助一个数组保存每两个三进制的运算结果，将该数组与每个三进制数进行运算，得到最后的结果

var singleNumber = function (nums) {
  if (nums.length === 1) {
    return nums[0]
  }
  const k = 3 //三进制
  // 10进制转k进制
  function toTernary (num) {
    var arr = []
    let flag = num < 0
    if (flag) num = -num
    while (num !== 0) {
      arr.push(num % k)
      num = Math.floor(num / k)
    }
    // 负数处理
    if (flag) {
      arr[32] = 1
    } else {
      arr[32] = 0
    }
    return arr
  }
  // k进制转10进制
  function toDecimal (ternary) {
    let sum = 0
    let base = 1
    for (let i = 0; ternary[i] !== void 0; i++) {
      sum += ternary[i] * base
      base *= k
    }
    // 负数处理
    return ternary[32] ? -sum : sum
  }
  // 2个k进制按位加，不进位
  function bitAdd (arr1, arr2) {
    let i = 0;
    while (arr1[i] !== void 0 && arr2[i] !== void 0) {
      arr1[i] = (arr1[i] + arr2[i]) % k
      i++
    }
    while (arr2[i] !== void 0) {
      arr1[i] = arr2[i++]
    }
    arr1[32] = (arr1[32] + arr2[32]) % k
  }
  let res = toTernary(nums[0])
  for (let i = 1; i < nums.length; i++) {
    bitAdd(res, toTernary(nums[i]))
  }
  return toDecimal(res)
};

时间复杂度满足了，但是引入了额外的数组，不满足本题 不使用额外空间 的要求。

不过该做法可以拓展到k进制，即 其余数字出现k次，求只出现一次的数字

思路2：二进制累加

由于三进制没法用 O(1) 空间表示。

当然也可以不用数组，用一个 int32 数字即可表示，但是按位叠加的时候，前一个的 10进制转k进制 处理又得重新做，增加了耗时

因此我们考虑用二进制的做法。

来自 Ant 的分享：

将每个数想象成32位的二进制，对于每一位的二进制的1和0累加起来必然是3N或者3N+1， 为3N代表目标值在这一位没贡献，3N+1代表目标值在这一位有贡献(=1)，然后将所有有贡献的位|起来就是结果。这样做的好处是如果题目改成K个一样，只需要把代码改成cnt%k，很通用

代码如下：

var singleNumber = function (nums) {
  if (nums.length === 1) {
    return nums[0]
  }
  const k = 3 //三进制
  let base = 1
  let res = 0
  for (let i = 0; i < 32; i++) {
    let cnk = 0
    for (let j = 0; j < nums.length; j++) {
      cnk += nums[j] & base ? 1 : 0
    }
    if (cnk % 3 !== 0) {
      res |= base
    }
    base <<= 1
  }
  return res
};

时间复杂度为 O(k*N) k为32 空间复杂度 O(1)

[francecil]

思路3：逻辑电路-最优解法

思路2 的时间复杂度还是太高了，有没有 O(N) 时间复杂度且不引入新的变量的解法呢？

参考 这个思路

一个2进制数 x 用两个变量a、b表示。对于 x 的第 i 位 x[i] ，可以用 a[i],b[i] 来表示

当 (a[i]b[i]) =00 时, x[i] = 0
当 (a[i]b[i]) = 01 || 10 时，x[i] = 1
即 x[i]= a[i] | b[i]

a[i]b[i] 的值按 00=>01=>10=>00 的顺序传递，
a[i] =1 表示该位置出现2次

// 设 x = nums[t] ,表示当前所遍历的数字
if (x[i] === 0) {
  // a[i] b[i] 均不变
} else {
  a[i] = a[i] | (b[i] & 1) // b[i]==1 && x[i]==1 时才进1
  b[i] = b[i] ^ 1 // 进1 0=>1，1=>0
  // 若 a[i]=b[i]=1 则a[i]=b[i]=0
  a[i] ^= (a[i] & b[i]) // a[i] & b[i] 为1时 a[i]=0 否则不变
  b[i] ^= (a[i] & b[i])
}
// 综合下即，
a[i] = a[i] | (b[i] & x[i])
b[i] = b[i] ^ x[i]
c[i] = (a[i] & b[i])
a[i] ^= c[i]
b[i] ^= c[i]

// 换句话说
a = a | (b & x)
b = b ^ x
c = (a & b)
a = a ^ c
b = b ^ c

举例分析，对于 010,001,010,010 ，

1. a=000,b=010,res=010
2. a=a|(b&x)=000,b=b^x=011,res=011
3. a=010,b=001,res=011
4. a=000,b=001,res=001

var singleNumber = function (nums) {
  if (nums.length === 1) {
    return nums[0]
  }
  let a = 0
  let b = nums[0]
  for (let i = 1; i < nums.length; i++) {
    a = a | (b & nums[i])
    b = b ^ nums[i]
    let c = (a & b)
    a = a ^ c
    b = b ^ c
  }
  return a | b
};

对上面的位运算继续优化，我们发现先考虑 b 的话可以避免一些运算

b[i] = b[i] ^ x[i] // 进1 0=>1，1=>0
b[i] = b[i] & ~a[i] // 之前 a[i] = 1 时，此次 b[i] 只能为 0
a[i] = a[i] ^ x[i] // 进1 0=>1，1=>0
a[i] = a[i] & ~b[i] // 本次计算出来 b[i] = 1,说明本次是从 00=>01 但是上一步让a[i]=1了 此处应该置为0
// 即
b = (b ^ x) & ~a;
a = (a ^ x) & ~b;

最佳代码

var singleNumber = function (nums) {
  if (nums.length === 1) {
    return nums[0]
  }
  let a = 0
  let b = nums[0]
  for (let i = 1; i < nums.length; i++) {
    b = (b ^ nums[i]) & ~a;
    a = (a ^ nums[i]) & ~b;
  }
  return a | b
};

[francecil]

解法三考虑拓展到 其余元素出现k次 ?