只出现一次的数字

Leetcode上有两道这样的题：

Single Number: Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Single Number II: Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

第一道题我很多年前就见过做过，思路其实很简单也很巧妙，就是利用 x ^ x == 0 和 x ^ 0 == x 这两条XOR的性质，将出现两次的数字互相抵消，从而使得最终的结果为只出现一次的数字，相应的代码如下：

pub fn single_number(nums: Vec<i32>) -> i32 {
    nums.into_iter()
        .fold(0, |init, val| init ^ val)
}

相比之下，第二道就难很多了，虽然题目只变了一处，只是把其余数字的出现次数由2次改为了3次，这一下题目的难度就直线上升了。

这里我们暂时不讨论这个问题具体如何解决，而是先把问题推广到更一般的形式

Single Number III: 给一个非空的整数数组，其中有一个元素出现了k(k >= 1)次，其余元素均出现了p(p > 1且k % p != 0)次，请问如何找出其中出现了k次的那个元素。

在回答这个问题之前，我们可以先思考一下为什么第一题可以这样做，比如第一题的情况，实际上只要k为奇数，p为偶数，都可以这样解决。这其实很像在计数，只不过我们只在乎总数为奇数还是偶数，也就是计数的二进制表示最后一位是1还是0，我们可以通过所有这些数字每个位上1的总数来考虑这个问题，那些出现过p次的数，他们的2进制表示里的每个1都肯定出现了p次，而我们要找的数，则是出现了k次（注意 k % p != 0 ），也就是说，如果我们计数的结果中某一位1出现的次数不能被p整除，那么我们要找的数的对应这1位肯定为1，否则为0。另一种等价的处理是我们希望最后计数的结果是 n % p ，当这个位上出现了p次1时，其最后计数正好抵消为0，这样最终我们只需要检查某个位上的计数是否为0，就可以知道这个位应该是0还是1。也就是说，我们希望有一种特殊的p进制数字，其加法没有进位。在第一题的情况里，就是我们需要没有进位的2进制数，而在2进制下没有进位的加法，实际就是XOR。

如果按照这个思路，直觉上来说我们可以怎么做呢？很简单：

pub fn single_number<const P: usize>(nums: Vec<i32>) -> i32 {
    let cnt = nums.into_iter()
        .fold([0; 32], |mut init, val| {
            for i in 0..32 {
                if 1 << i & val != 0 {
                    // 这里我们保留完整的计数，在下面对计数值进行判断
                    init[i] += 1;
                }
            }
            init
        });
    cnt.into_iter()
        .enumerate()
        .fold(0, |init, (idx, cnt)| match cnt % P {
            0 => init,
            _ => init |= 1 << idx,
        })
}

也就是说，我们使用一个 [i32; 32] 数组来为单独每个位计数，凡是出现了p的整数倍的位我们都置为0，其余位置为1，这样我们就轻松解决了这个更一般的问题。

那么我们能不能进一步“简化”这个做法呢？答案是可以的，因为相对来说我们的P是很小的，而我们用一个 i32 来计数是非常浪费的，我们只需要 $n = \lceil \log_2^p \rceil $ 这么多位就够了。也就是说用一个 [i32; n] 来做计数就够了，代价则是我们需要“转置“这个计数数组，也就是说这n个 i32 的同一个位共同构成了这个位的计数器，而我们则需要进一步推导这里计数的“加法规则”。因为所有位的计数都是完全独立的，我们可以只考虑一个位的情况，然后推广到32位即可。

考虑一个1位的整数 i1 ，我们使用一个 [i1; n] 数组来对其进行计数，假设这里p是3，则n=2，我们有如下真值表：

设该位数字为 x ，计数为 [c1, c0] ，通过简单的逻辑代数，我们有如下状态转化方程:

c0' = !c0 & !c1 & x | c0 & !c1 & !x
c1' = c0 & !c1 & x | !c0 & c1 & !x

化简得到

c0' = !c1 & (c0 ^ x)
c1' = c0 & x | c1 & !x (这里能化简的原因是我们不在乎[1, 1]的状态转化)

最终 c0 | c1 的结果就是我们的计数器是否为0，推广到32位数字，我们的计数器则是 [i32; n] ，那么我们有如下代码

pub fn single_number(nums: Vec<i32>) -> i32 {
    nums.into_iter()
        .fold([0, 0], |[c1, c0], x|
            [ c0 & x | c1 & !x, (c0 ^ x) & !c1 ]
        )
        .into_iter()
        // 任意位不为0都说明计数不为0
        .fold(0, |init, val| init | val)
}

这样我们就解决了p为3的问题，通过相同的思路，我们可以解决任意p的问题，区别只在于不同p的化简难度不同。

其实自己做这个题的时候卡了很久也做不出来，思维已经陷入怎么构造位运算来抵消3个数字了，看到题解确实有一种醍醐灌顶的感觉。解决这种问题最重要的还是思路，如果能想到对每一位上的数字做计数，其实已经离正确答案不远了。

参考：

Detailed explanation and generalization of the bitwise operation method for single numbers

Concise solution with Ternary logic || Explained