Given an array of integers, every element appears three times except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using
extra memory?
之前在Quora上看到一个用两个变量ones和twos分别统计1和2出现的次数来模拟“三进制”的方法。这次在网上又看到另一种解法也很不错，用一个长度为32的数组来统计每个位上1出现的次数，次数总和为3的倍数表明我们要求的数在该位是0，否则为1.
public int singleNumber2(int[] A) { /* 注释内为用ones和twos统计1和2出现次数的解法
int ones=0,twos=0;
int n=A.length; //int result=A[0]; for(int i=0;i<n;i++) { int tmp=ones; ones=(tmp^A[i])&(~twos); twos=(tmp&A[i])|(twos&(~A[i])); } return ones; */ int[] count=new int[32]; for(int i=0;i<A.length;i++) { int num=A[i]; for(int j=0;j<32;j++) { if((num&(1<<j))!=0) count[j]++; } } int ans=0; for(int i=0;i<32;i++) { if(count[i]%3!=0) ans+=1<<i; } return ans; }
原文：http://www.cnblogs.com/developerY/p/SingleNumber2.html