剑指 Offer 56 - II. 数组中数字出现的次数 II

与LeetCode 137相同，有一组数不合群，其他都出现3次，就他只出现1次。

  1. //按位取 异或，时间nlogC 空间O1;通用版本             logC = 32
  2. func singleNumber(nums []int) int {
  3.     number, res := 0, 0 
  4.     for i := 0; i < 64; i++ { 
  5.         number = 0
  6.         for _, k := range nums { 
  7.             number += (k >> i) & 1            //通过右移i位的方式，计算每一位1的个数
  8.         }
  9.         res |= (number) % 3 << i                //最终将抵消后剩余的1放到对应的位数上
  10.     }
  11.     return res
  12. }
//数字电路，时间On，空间O1
func singleNumber(nums []int) int {
    a, b := 0, 0
    for _, num := range nums {
        b = (b ^ num) &^ a
        a = (a ^ num) &^ b
    }
    return b
}