Given 3*n + 1 numbers, every numbers occurs triple times except one, find it.

Given [1,1,2,3,3,3,2,2,4,1] return 4

 

法1：加和掩码提取位，模三，加到结果里。int 数据共有32位，针对其中具体某一位，可以用掩码（>>操作和 &1操作）把所有数字的这一位都加起来。针对重复3次的数字，他们加的和%3必定为0（0*3 %3 ==0， 1*3 %3 ==0），那么所有的和%3得到的必定就是寻找的数在这一位上到底是1还是0了。把这一位<<，并且加到res变量返回即可。

 

public class Solution {    /**     * @param A : An integer array     * @return : An integer      */    public int singleNumberII(int[] A) {        // write your code here        int res = 0;        for (int i = 0; i < 32; i++){            int rsBit = 0;            for (int idx = 0; idx < A.length; idx++){                int bit = A[idx] >> i;                bit &= 1;                rsBit += bit;            }            rsBit %= 3;            res += rsBit << i;        }        return res;    }}

 

法2：利用三个变量分别保存各个二进制位上 1 出现一次、两次、三次的分布情况，最后只需返回变量一。

1. 代码使得这三个变量表现形式是： 某数第一次出现- 100，某数第二次出现-010，某数第三次出现- 111（后续抹去变为001）。所以如果某个数是只出现一次(3n+1)，它的特征位会被保留在ones中，如果某个数是出现正好两次(3n+2)，它的特征位会被保留在twos中。

2. 小心一下循环里要先处理2再处理1。

3. |= 是想做赋一处理，&= 是想做归零处理。^= 是想做“突出奇数次特征位，抹平偶数次特征位”处理。

public class Solution {    /**     * @param A : An integer array     * @return : An integer      */    public int singleNumberII(int[] A) {        // write your code here        int ones = 0, twos = 0, threes = 0;                for(int i = 0; i < A.length; i++){            //某数第一次进来，ones twos threes  1 0 0            //某数第二次进来，ones twos threes  0 1 0            //某数第三次进来，ones twos threes先1 1 1, 后 0 0 1            //某数第四次进来，ones twos threes  1 0 0            //循环            twos |= ones & A[i];            ones ^= A[i];            threes = ones & twos;            //第三次来时抹去一二痕迹            twos &= ~three;            ones &= ~three;        }                return ones;    }}