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

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

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

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

用异或运算可以找出 1 个只出现一次的数字。而如果这样的数字有 2 个，异或运算的结果就是它们俩异或的结果。

根据他们俩异或的结果，从右开始找到第一位不相同的数字，用这一位数字为 0 或 1 就能将整个数组分成两半，同时这两个只出现了一次的数也被分开了。

再次循环判断数组，这一位为 1 的组成一组异或，为 0 的组成另一组异或，得到的结果就是这两个只出现了一次的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func singleNumbers(nums []int) []int {
    res, index := 0, 0
    for _, n := range nums {
        res ^= n
    }

    //  检查这两个只出现一次的数从哪一位开始不同
    for res & 1 == 0 {
        index ++
        res >>= 1
    }

    // 用这不同的一位分割数组，从而分开两个只出现一次的数
    r1, r2 := 0, 0
    for _, n := range nums {
        if n >> index & 1 == 0 {
            r1 ^= n
        } else {
            r2 ^= n
        }
    }

    return []int{r1, r2}
}

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

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

如果一个数字出现 3 次，它的二进制每一位也出现的 3 次。

如果把所有的出现 3 次的数字的二进制表示的每一位都分别加起来，那么每一位都能被 3 整除。

我们把数组中所有的数字的二进制表示的每一位都分别加起来。

  • 如果某一位能被 3 整除，那么这一位对只出现一次的那个数的这一肯定为 0。
  • 如果某一位不能被3整除，那么只出现一次的那个数字的该位置一定为 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func singleNumber(nums []int) int {
    digitsSum := make([]int, 32) // 题目限制最多 32 位

    // 统计每一位的出现次数
    for _, n := range nums {
        for j := range digitsSum {
            digitsSum[j] += (n >> j) & 1
        }
    }

    // 每一位的和都整除 3，哪一位不能整除，则说明只出现一次的数字这一位为 1
    res := 0
    for i := 31; i >= 0; i-- {
        res = res << 1
        if digitsSum[i] % 3 == 1 {
            res |= 1
        }
    }

    return res
}