Leetcode 137. 只出现一次的数字II

(Updated: )
(2 mins to read)

题意

一个数组中有一个数字只出现了1次， 其余数字都出现了K次 (K > 1)，问出现1次的数字是什么

做法

按照二进制逐位确定即可，如果该位1的个数出现的次数为nk + 1，说明出现1次的数字包含该位。

遇到的一个坑是Go语言中的int的大小是和操作系统的位数有关的，在64位上是8字节（类似于C++中的size_t）。

当时用默认的int WA了之后，我以为是有符号数位移，以及有符号数溢出未定义导致的问题。

记录一下：

  • 左移低位补0即可，逻辑移位和算术移位一样
  • 有符号数右移是算术移位，高位补符号位
1
2
3
4
5
6
7
8
9
10
11
12
13
func singleNumber(nums []int) int {
    var ans int32 = 0
    for i := 0; i < 32; i++ {
        cnt := 0
        for _, num := range nums {
            cnt += (num >> i) & 1
        }
        if cnt % 3 == 1 {
            ans |= (1 << i)
        }
    }
    return int(ans)
}

这里如果var用默认的int类型取值可能大于等于$2^{31}$，此时再转int32也是未定义行为。

当k很小时，可以自行构造位运算。比如k=2时用异或，k=3时为(0, 0)->(0, 1)->(1, 0)->(0, 0)…，

1
a, b = (a ^ x) & (a | b), (b ^ x) & ~a