Single Number II

Q:
Given an array of integers, every element appears three times except for one. Find that single one.
Could you implement it without using extra memory?

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

A:
      -------4th pass -------idea  borrowed from EPI------------
用 zeros, ones, twos 3个变量代表每个bit上的积累的1的count%3 是多少。（每个bit，有且只有一个为1）
然后，每次计算的时候，该bit要得到 1，有2种情况。
1： 下一位是1，且新来的A[i]为1 （进位的结果）
2 ： 本来是1， 且新来的A[i] 为0 ， （承袭之前的结果，没有变化）

public class Solution {
    public int singleNumber(int[] A) {
        int zeros = -1, ones = 0, twos = 0; // result is the ones, -1 is OB1111.1111
        for(int i =0;i<A.length;i++){
            int old0 = zeros, old1 = ones, old2 = twos;
            zeros =(old2 & A[i]) | (old0 & ~A[i]);
            ones = (old0 & A[i]) | (old1 & ~A[i]);
            twos = (old1 & A[i]) | (old2 & ~A[i]);
        }
        return ones;
    }
}

   -------3th pass -------idea  borrowed from EPI------------
用one，two两个int变量，代表，每一个bit，我们发现的1的次数。
这里，为了不额外声明空间，我们用了A[0],A[1]两个位置。
这里，比较tricky的地方就是 我们在计算初始的A[0],A[1]的时候，需要先计算A[0]，再利用新的A[0]和旧的A[1]来计算A[1]。
然后在循环里，我们先计算A[1]，再利用这个新的A[1]来 计算A[0]

public class Solution {
    public int singleNumber(int[] A) {
        if(A.length==1)
            return A[0];
        // A[0] is the the time that 1 occurs in odd number, A[1] is the even number,
        A[0] ^= A[1]; // this is the lower bit
        A[1] &= ~A[0]; // high bit,  but calculated use the new A[0]
        for(int i = 2;i<A.length;i++){
            A[1] = ~A[1] & (A[0] &A[i]) | A[1] & ~(A[0]&A[i]);   // for bits 2,
            A[0] = (A[0]| A[i]) & ~(A[0]&A[i]&A[1]); // for bits 1
        }
        return A[0] & ~(A[0]&A[1]);
    }
}

仔细体会吧，  Tiger, 貌似EPI上有更简单的算法，哦，这里， A[1] 代表高位，A[0]代表低位。  注意处理11的情况，这时候，我们要把他们当作00来对待。




-----------------第二遍，-----------都是数每一个位置，1的个数--

网上的一个做法是： 对于除出现一次之外的所有的整数，其二进制表示中每一位1出现的次数是3的整数倍，将所有这些1清零，剩下的就是最终的数。 用ones记录到当前计算的变量为止，二进制1出现“1次”（mod 3 之后的 1）的数位。用twos记录到当前计算的变量为止，二进制1出现“2次”（mod 3 之后的 2）的数位。当ones和twos中的某一位同时为1时表示二进制1出现3次，此时需要清零。即用二进制模拟三进制计算。最终ones记录的是最终结果。 时间复杂度：O（n）

public class Solution {
    public int singleNumber(int[] A) {
        int n = A.length;
        // use 32 bit to count
        int result =0;
        for(int i =0;i<32;i++){
            int bit =0;
            for(int j =0;j<n;j++)
                bit = ((A[j]>>i&1)+bit)%3;
            result += bit<<i;
        }
        return result;
    }
}

错误：
1： if(   a & b != 0 ) // given a and b are integer
   这样是不对的，因为涉及到 &  != 的优先级关系， 会先计算 b!=0.
   导致  if （int & boolean ) 
2:   bit运算中， 没有 ||  && 这些， 那些只是逻辑运算。


1： 全1 的int类型是  int res = Integer.MIN_VALUE-1 （其实直接就是-1）;
而真正的Integer.MIN_VALUE  是  1000......0000(31个0）。



既然，不让用extra space，但是又不能不用一点儿space, 就只好在数组里更改数值了。

扩展一：
给定一个包含n个整数的数组，除了一个数出现二次外所有的整数均出现三次，找出这个只出现二次的整数。ones记录1出现一次的数，twos记录1出现2次的数，容易知道twos记录的即是最终结果。

扩展二：
给定一个包含n个整数的数组，有一个整数x出现b次，一个整数y出现c次，其他所有的数均出现a次，其中b和c均不是a的倍数，找出x和y。使用二 进制模拟a进制，累计二进制位1出现的次数，当次数达到a时，对其清零，这样可以得到b mod a次x，c mod a次y的累加。遍历剩余结果（用ones、twos、fours...变量表示）中每一位二进制位1出现的次数，如果次数为b mod a 或者 c mod a，可以说明x和y的当前二进制位不同（一个为0，另一个为1），据此二进制位将原数组分成两组， 一组该二进制位为1，另一组该二进制位为0。这样问题变成“除了一个整数出现a1次（a1 = b 或 a1 = c）外所有的整数均出现a次”，使用和上面相同的方式计算就可以得到最终结果，假设模拟a进制计算过程中使用的变量为ones、twos、 fours...那么最终结果可以用ones | twos | fours ...表示。