Single Number II

Discuss

由于其他数字都出现了三次，所以把所有数的第n个bit上的1加起来，一定是3的倍数，或者%3为1。因为如果没有那个单个出现的数，把所有数的第n个bit上的1加起来一定是3的倍数。加了那个单个出现的数之后，如果那个数在这位上是1，那么和就是%3为1了。反之，如果那位为零，就是3的倍数了。

推广到所有其他数出现了n>=3次，只有一个数出现一次，都是这个道理。

public class Solution {
    public int singleNumber(int[] A) {
       int arr[] = new int[33]; 
       //and the number on every bit,and add the bits
       for(int i=0;i<=31;i++)
       {
           int bit = 1<<i;
           // the bits is 2^31
           for(int j=0;j<A.length;j++)
           {
               // this must be unequal, not bigger than
               if((A[j]&bit)!=0)
               {
                   arr[i]++;
               }
           }
       }
       int res = 0;
       // reconstruct the number
       for(int i=0;i<=31;i++)
       {
           if(arr[i]%3!=0)
           {
               res += 1<<i;
           }
       }
        return res;
    }
}

Single Number II,布布扣,bubuko.com

Single Number II

原文：http://blog.csdn.net/nan327347465/article/details/38346723