出现一次的数字ii

// discuss.leetcode.com/topic/22821/an-general-way-to-handle-all-this-sort-of-questions/1

public class Solution {
    public int singleNumber(int[] A) {
        int a = 0 , b = 0;
        for(int c : A){
            int ta,tb;
            ta = a;
            tb = b;
            a = (ta&(~tb)&(~c))|((~ta)&tb&c);
            b = ~ta&((~c&tb)|(~tb&c));
        }
        return a|b;
    }
}

//由于只有一个出现一次的数字，其余都是出现三次，那么有如下思路
// 针对于序列中出现三次的所有数字的每一位来说，相加的结果只有两种
//1+1+1==3 或者0+0+0=0
//那么再加上只出现一次的数字的对应位数字的话，也有两种0或者4
//所以我们可以对上述的每一位求和之后对3取余，结果将会是1或者0
//也就是代表了出现一次的的这个数字对应位置上是1或者0
public class Solution {
    public int singleNumber(int[] A) {
        if(A == null||A.length == 0){
            return -1;
        }
        //得到出现一次的数字的值】
        int result = 0;
        //int为4个字节，那么一共有4*8=32位
        for(int i = 0;i < 32;i++){
            //保存每一位求和值
        	int sum = 0;
            for(int j = 0;j < A.length;j++){
                //累加所有数字上第i位上的数字
                sum+=(A[j]>>i)&1;
            }
            //取余得到第i位上的数字，之后更新result
            result |= (sum % 3) << i;
        }
        return result;
    }
}

😁解法一复杂度（n）     解法较复杂 经典！！（内含详细推导，包括真值表，卡诺图）
😀解法二复杂度（32n） 解法较容易  时间复杂度会随数据类型不同增减

解法一解析： 将数据转换为二进制，对数组元素每一位的二进制的1或0累加起来必然是3N或者3N+1。

考虑使用模3加法:    sum = (sum + c) % 3;

对数组元素循环应用模3加法后，最后的结果中，每一位的sum为0或1，该二进制数表示的即为只出现一次的数组元素。

sum可取得值为0、1、2，但是二进制数的每一位只能表示0和1，因此考虑使用两个二进制数（a, b）去表示sum中的高,低位。则0（00）， 1（01），2（10）

最后结果串中，高位字符串全为0，低位字符串即为正确结果。

真值表：

公式： (ab(旧) + c) % 3 = ab(新)  // a是高位 b是低位

例：二进制： (10 + 1) % 3 = 00

十进制： (2 + 1) % 3 = 0

卡诺图 b(新):

逻辑表达式：

a(新) = (~c & a(旧) & ~b(旧)) | (c & ~a(旧) & b(旧))

b(新) = (~c & ~a(旧) & b(旧)) | (c & ~a(旧) & ~b(旧))

将数组A中每个元素应用上述表达式累加后，得到的结果即为：

高位 : 一个全为0的字符串 （逢3消0，只剩下出现1次的那个数）

低位 : 一个零一串，它表示的正是只出现1次的数的二进制表示

代码：

class Solution {
public:
    int singleNumber(int A[], int n) {
        if (n == 0) return 0;
        int a = 0;
        int b = 0;
        int c;
        int ta, tb;
        for (int i = 0; i < n; i++) {
            c = A[i];
            ta = a;
            tb = b;
            a = (~c & ta & ~tb) | (c & ~ta & tb);
            b = (~c & ~ta & tb) | (c & ~ta & ~tb);
        }
        return b;
    }
};

解法二解析：

将数据转换为二进制，对数组元素每一位的二进制的1或0累加起来必然是3N或者3N+1。Int类型是4字节32位，循环32次，每次循环记录数组元素当前位的二进制累加和，然后将模三后的结果（0或1）放置在对应位，循环结束即可得到只出现一次的数的二进制表示。

代码：

class Solution {
public:
    int singleNumber(int A[], int n) {
        int sum;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            sum = 0;
            for (int j = 0; j < n; j++) {
                sum += (A[j] >> i) & 1;
            }
            res |= ((sum % 3) << i);
        }
        return res;
    }
};

思路都差不多，但感觉这样改一下顺序会更加直观：

three完全不依赖前一个three，只依赖于前一个two，所以可以把three先确定下来；

实际上只是维护了one和two，three等同于zero，只是用作辅助，用于把one中的three的部分归零。

public class Solution {
    public int singleNumber(int[] A) {
        int one=0,two=0;
        for(int a:A){
            int three=two&a;
            two=(two&~a)|(one&a); 
            one=one^a&(~three);
        }
        return one|two;
    }
}

public class Solution {
    public int singleNumber(int[] A) {
        /**
         * ones:出现1次的bits
         * twos:出现2次的bits
         * threes:出现3次的bits
         * ones = threes & ~twos
         * twos = threes & ~ones
         * 
         * */
        int ones = 0, twos=0;
        for(int i = 0; i < A.length; i++) {
            //xxxs ^ A[i] = threes
            ones = (ones ^ A[i]) & ~twos;
            twos = (twos ^ A[i]) & ~ones;
        }
        return ones;
    }
}
参考了:https://leetcode.com/problems/single-number-ii/discuss/ 

class Solution {
public:
    int singleNumber(int A[], int n) {
        //int size = sizeof(A);
        set<int> s1;
        set<int> s2;
        if(n<=0)
            return 0;
         
        for(int i=0;i<n;i++)
        {
            if(!s1.insert(A[i]).second)
                s2.insert(A[i]);
        }
        for(int i=0;i<n;i++)
        {
            if(s2.insert(A[i]).second)
                return A[i];
        }
        return 0;
    }
};

class Solution {
public:
    int singleNumber(int A[], int n) {

        int first = 0;
        int second = 0;
        for(int i = 0; i < n ; i++){
            int s = first & A[i] ;  //得出第二次出现位
            int t = second & s ;     //得出第三次出现位
            first |= A[i];           //first保留第一次出现位
            second |= s;             //second保留第二次出现位
            first ^= t;              //first 清空第三次出现位
            second ^= t;             //second清空第三次出现位
        }
        return first ;
    }
};
将每个数字都看成是二进制数，first记录第一次出现的二进制位，second记录第二次出现的二进制位，当二进制位出现三次的时候清空first和second的对应记录位。

看了你们的都用了位运算，所以发下非位运算的

import java.util.*;
public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] A) {
        // write code here
        Arrays.sort(A);
        for(int i=0;i<A.length-2;i+=3){
            if(A[i]!=A[i+1]){
                return A[i];
            }
        }
        return A[A.length-1];
    }
}

• idea：

  1. 当某一位出现三次时约掉
  2. 用two代表只出现过两次的位，one代表只出现过一次的位，appr代表需要约掉的位
  3. 在two与A[i]同时出现的位要约掉，即appr = two & A[i]
  4. 在one和A[i]同时出现的位要成为two，two除掉约去的位（即two ^ appr）也继续是two
  5. A[i]除去约掉的位（即A[i] ^ appr）成为one的候选者，将候选者与one异或即得迭代后的one。
  6. 遍历完以后，one即为只出现过一次（出现三次的都约掉了）的位，此时one即为只出现过一次的数。

• code

  class Solution {
  public:
    int singleNumber(int A[], int n) {
        if (n == 1) return A[0];
        if (n < 4) return -1;
        unsigned two=0, one=0, appr = 0;
        for (int i = 0; i < n; i++){
            appr = two & A[i]; //在two与A[i]同时出现的位要约掉
            two = (one & A[i]) | (two ^ appr); //在one和A[i]同时出现的位要成为two，two中出现appr（约掉）中没出现的位也要成为two
            one = one ^ A[i] ^ appr; //A[i]中出现appr中没出现的位成为one的候选者，将候选者与one异或即得迭代后的one。
        }
        return one;
    }
  };

class Solution {
public:
    /*
        思路：参考来源：https://leetcode.com/problems/single-number-ii/discuss/43296/an-general-way-to-handle-all-this-sort-of-questions
        这是一个通用的思路，对于类似的一个数组里除了一个数之外其他的数都重复了N次这样的问题，这样的思想可以通吃。
        设置a和b来记录bit操作，a是高位,b是低位，来数为c，对于每一位有：
        a    b    c    comingA    comingB
        0    0    0    0            0
        0    1    0    0            1
        1    0    0    1            0
        0    0    1    0            1
        0    1    1    1            0
        1    0    1    0            0
        注：这里因为是记录三进制的数，因此，不考虑a=1,b=1的情况
        由上图可知以下逻辑表达式：
        comingA=~a&b&c+a&~b+&~c;
        comingB=~a&b&~c+~a&~b&c;
        所以可以得到相应的C语言表达：
        comingA=(~a&b&c)|(a&~b&~c);
        comingB=(~a&b&~c)|(~a&~b&c);
        这样对于结果来说，每一位：
        a    b    res
        0    1    1
        1    0    2
        0    0    3
        由于题目中确定只有res=1和3的情况，因此，结果集每一位的表达简化为：
        a    b    res
        0    1    1
        0    0    0
        即res=a|b;
        以上。
    */
      int singleNumber(int A[], int n) {
        int a=0,b=0;
        for(int i=0;i<n;i++){
            int c=A[i];
            int tempA=(a&~b&~c)|(~a&b&c);
            b=(~a&b&~c)|(~a&~b&c);
            a=tempA;
        }
        return a|b;
    }
};

public class Solution {

    public static void main(String[] args) {
        int a[] = {2,2,3,2};
        System.out.println(singleNumber(a));
    }
    public static int singleNumber(int[] A) {
        if (A == null || A.length == 0) {
            return new Integer(null);
        }

        int bitSum[] = new int[32];

        for (int i = 0; i < A.length; i++) {
            int bitMask = 1;
            for (int j = 0; j < 32; j++) {
                int bit = A[i] & bitMask;
                if(bit != 0)
                bitSum[j] += 1;
                bitMask = bitMask << 1;
            }
        }

        int result = 0;
        int bitMask = 1;
        for (int i = 0; i < 32; i++) {
            int bit = bitSum[i] % 3;
            result += bitMask * bit;
            bitMask = bitMask << 1;
        }
        return result;
    }
}

import java.util.HashMap;
public class Solution {
    public int singleNumber(int[] A) {
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<A.length;i++){
            if(map.containsKey(A[i])){
                map.put(A[i],map.get(A[i])+1);
            }else{
                map.put(A[i],1);
            }
        }
        for(int key:map.keySet()){
            if(map.get(key)!=3){
                return key;
            }
        }
        return 0;
    }
}

思路：参考了菜鸟葫芦娃，学工程真是太好了，两位老哥的思路。
single numer本质就是用一个数记录每个bit出现的次数，当数的某一位出现了指定次数就归0（本题是3次）。
假设当出现2次就归0时，很容易想到可以使用异或的方法。
然而，当出现2次以上时，我们就需要增加记录的数，因为一个数每个bit，只有0，1两种可能，只能记录两种。
此处我们就需要使用两个数分别secondbit,firstbit来进行记录，可以表示4种可能，本题只需要3种00，01，10。

然后，使用卡诺图来得到secondbit,firstbit的表达式,分别简化secondbit,firstbit为符号f,s则有：
f卡诺图：

因此有： f = (~s&~f&A[i])|(~s&f&~A[i])

s卡诺图：

因此有： s = (~s&f&A[i])|(s&~f&~A[i])

此外当except one 可能出现1次，也可能出现2次。最后的 s f 可能为 00，01，10 结果就是 a|b，有1出现则此位置为1否则为0

    int singleNumber(int A[], int n) {
        int firstbit = 0,secondbit = 0;
        int one = 0;
        for(int i = 0;i < n; i++){
            one = firstbit;
            firstbit = (~secondbit&~firstbit&A[i])|(~secondbit&firstbit&~A[i]);
            secondbit = (~secondbit&one&A[i])|(secondbit&~one&~A[i]);
        }
        return firstbit|secondbit;
    }

同步博客

//one代表只出现了一次的位，two代表出现了两次的位，注意one置一的位two一定不为1，
//反过来一样，然后当出现三次时清零。class Solution {
public:
    int singleNumber(int A[], int n) {
        int one=0,two=0;
        for(int i=0;i<n;i++){
            int tmp=two&A[i];
            two^=tmp;//这两行将之前已经出现两次的位
            A[i]^=tmp;//清零
            
            tmp=one&A[i];
            one^=tmp;//这两行将已经出现了一次的位
            A[i]^=tmp;//清零
            two^=tmp;
            one^=A[i];
        }
        return one;
    }
};

class Solution {
public:
    int singleNumber(int A[], int n) 
    {
        if(A==nullptr || n<=0)
            return 0;
        vector<int>  res(32,0);
        for(int i=0;i<n;i++)
        {
            int bitMask = 1;
            for(int j=31;j>=0;j--)
            {
                int bit = A[i]&bitMask;
                if(bit!=0)
                    res[j] += 1;
                bitMask <<= 1;
            }
        }
        int result = 0;
        for(int i=0;i<32;i++)
        {
            result = result<<1;
            result += res[i]%3;
        }
        return result;
    }
};

class Solution {
public:
    int singleNumber(int A[], int n) {
        int bitnum[32]={0};
        int res=0;
        for(int i=0;i<32;i++){
            for(int j=0;j<n;j++){
                bitnum[i]+=(A[j]>>i)&1;
            }
            res|=(bitnum[i]%3)<<i;
        }
        return res;
    }
};

	public int singleNumber(int[] A) {



	        //discuss.leetcode.com/topic/22821/an-general-way-to-handle-all-this-sort-of-questions/1



	        //这里面有详解，这里主要说一下思想



	        //因为出现的是三次，所以需要设计成一个数出现3次之后自动会变为0，这就代表不影响后面的数



	      //现在只用bit来表示，a，b可能是0,1的组合，c(next bit)可能是0或者1



	        //采用两位a,b来表示.  a ，b 的值可能为0 0 ，0 1 ，10



	        //分别代表0次，1次，2次。不可能出现1 1。因为3次之后就清0了



	 //当对应不同的数字时，无非就是把一位的情况扩展到了32位。但逻辑运算（对于每一位的仍然一样）



	        int a = 0;



	        int b = 0;



	        int ta = 0;



	        for(int c : A){



	            ta = (~a & b & c) | (a & ~b & ~c);  //这里之所以需要使用ta，是因为计算b的时候需要a的旧值



	            b = (~a & ~b & c) | (~a & b & ~c);



	            a = ta;



	        }



	        //we need find the number that is 01,10 => 1, 00 => 0.



	        //return a|b 意思是返回出现一次或者出现两次的那个数(假设不知道一个数是出现了一次还是两次)



	        //不管只有一个数出现了一次还是两次，另一个数一定为0；相或即可



	        return a | b;



	}