只出现一次的数字II

来源Leetcode第137题只出现一次的数字II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3

排序后遍历

思路同136题，排序后遍历

public int singleNumber(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length - 1;
    for(int i = 0;i < nums.length ;){
        if(i == len){
            return nums[i];
        }else if(nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2]) {
            i += 3;
        }
        else if(nums[i] != nums[i + 1])
            return nums[i];
    }
    return 0;
}

位运算

来源题解

将问题一般化

给一个数组，每个元素都出现 k ( k > 1) 次，除了一个数字只出现 p 次(p >= 1, p % k !=0)，找到出现 p 次的那个数。
考虑其中的一个 bit
为了计数 k 次，我们必须要 m 个比特，其中 2^m >=k，也就是 m >= log2k。
假设我们 m 个比特依次是 x_mx_{m-1}…x_2x_1x 。
开始全部初始化为 0。00…00。
然后扫描所有数字的当前 bit 位，用 i 表示当前的 bit。

假如例子是 1 2 6 1 1 2 2 3 3 3, 3 个 1, 3 个 2, 3 个 3,1 个 6
1 0 0 1
2 0 1 0
6 1 1 0
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1
3 0 1 1
3 0 1 1
初始状态 00…00。
第一次遇到 1 , m 个比特依次是 00…01。
第二次遇到 1 , m 个比特依次是 00…10。
第三次遇到 1 , m 个比特依次是 00…11。
第四次遇到 1 , m 个比特依次是 00..100。

x1 的变化规律就是遇到 1 变成 1 ，再遇到 1 变回 0。遇到 0 的话就不变。
所以 x1 = x1 ^ i，可以用异或来求出 x1 。
那么 x2…xm 怎么办呢？
x2 的话，当遇到 1 的时候，如果之前 x1 是 0，x2 就不变。如果之前 x1 是 1，对应于上边的第二次遇到 1 和第四次遇到 1。 x2 从 0 变成 1 和从 1 变成 0。
所以 x2 的变化规律就是遇到 1 同时 x1 是 1 就变成 1，再遇到 1 同时 x1 是 1 就变回 0。遇到 0 的话就不变。和 x1 的变化规律很像，所以同样可以使用异或。
x2 = x2 ^ (i & x1)，多判断了 x1 是不是 1。
x3，x4 … xm 就是同理了，xm = xm ^ (xm-1 & … & x1 & i) 。
再说直接点，上边其实就是模拟了每次加 1 的时候，各个比特位的变化。所以高位 xm 只有当低位全部为 1 的时候才会得到进位 1 。

00 -> 01 -> 10 -> 11 -> 00

上边有个问题，假设我们的 k = 3，那么我们应该在 10 之后就变成 00，而不是到 11。
所以我们需要一个 mask ，当没有到达 k 的时候和 mask进行与操作是它本身，当到达 k 的时候和 mask 相与就回到 00…000。
根据上边的要求构造 mask，假设 k 写成二进制以后是 km…k2k1。
mask = ~(y1 & y2 & … & ym),
如果kj = 1，那么yj = xj
如果 kj = 0，yj = ~xj 。

举两个例子。

k = 3: 写成二进制，k1 = 1, k2 = 1, mask = ~(x1 & x2);

k = 5: 写成二进制，k1 = 1, k2 = 0, k3 = 1, mask = ~(x1 & ~x2 & x3);

很容易想明白，当 x1x2…xm 达到 k1k2…km 的时候因为我们要把 x1x2…xm 归零。我们只需要用 0 和每一位进行与操作就回到了 0。
所以我们只需要把等于 0 的比特位取反，然后再和其他所有位相与就得到 1 ，然后再取反就是 0 了。
如果 x1x2…xm 没有达到 k1k2…km ，那么求出来的结果一定是 1，这样和原来的 bit 位进行与操作的话就保持了原来的数。
总之，最后我们的代码就是下边的框架。

for (int i : nums) {
    xm ^= (xm-1 & ... & x1 & i);
    xm-1 ^= (xm-2 & ... & x1 & i);
    .....
    x1 ^= i;
    
    mask = ~(y1 & y2 & ... & ym) where yj = xj if kj = 1, and yj = ~xj if kj = 0 (j = 1 to m).

    xm &= mask;
    ......
    x1 &= mask;
}

考虑全部 bit

假如例子是 1 2 6 1 1 2 2 3 3 3, 3 个 1, 3 个 2, 3 个 3,1 个 6
1 0 0 1
2 0 1 0
6 1 1 0
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1
3 0 1 1
3 0 1 1
之前是完成了一个 bit 位，也就是每一列的操作。因为我们给的数是 int 类型，所以有 32 位。所以我们需要对每一位都进行计数。有了上边的分析，我们不需要再向解法三那样依次考虑每一位，我们可以同时对 32 位进行计数。
对于 k 等于 3 ，也就是这道题。我们可以用两个 int，x1 和 x2。x1 表示对于 32 位每一位计数的低位，x2 表示对于 32 位每一位计数的高位。通过之前的公式，我们利用位操作就可以同时完成计数了。

返回什么
最后一个问题，我们需要返回什么？
因为所有的数字都出现了 k 次，只有一个数字出现了 p 次。
因为 xm…x2x1 组合起来就是对于每一列 1 的计数。
如果 p = 1，那么如果出现一次的数字的某一位是 1 ，一定会使得 x1 ，也就是计数的最低位置的对应位为 1，所以我们把 x1 返回即可。对于上边的例子，就是 110 ，所以返回 6。
如果 p = 2，二进制就是 10，那么如果出现 2次的数字的某一位是 1 ，一定会使得 x2 的对应位变为 1，所以我们把 x2 返回即可。
如果 p = 3，二进制就是 11，那么如果出现 3次的数字的某一位是 1 ，一定会使得 x1 和x2的对应位都变为1，所以我们把 x1 或者 x2 返回即可。

public int singleNumber(int[] nums) {
    int x1 = 0, x2 = 0, mask = 0;
    for (int i : nums) {
        x2 ^= x1 & i;
        x1 ^= i;
        mask = ~(x1 & x2);
        x2 &= mask;
        x1 &= mask;
    }
    return x1; 
}

三进制运算

摸了

class Solution {
    public int singleNumber(int[] A) {
        int ones = 0, twos = 0;
        for (int i = 0; i < A.length; i++) {
            ones = (ones ^ A[i]) & ~twos;
            twos = (twos ^ A[i]) & ~ones;
        }
        return ones;
    }
}