Single Number II

	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?
	Cause of the constrain of linear time complexity, so one loop may be work
	also beacause of the the hint of without using extra memory, so a 32 length int array should be a
	good choice.
	use this array to count the appear times of 1 at each bit, use %3 to ignore the number appear 3 times
	then use | to build left number, because only one number appear onece, so the left number is the number is which
	we want.
	public class Solution {
	public int singleNumber(int[] A) {
	if (A==null||A.length==0){
	return -1;
	}
	int[] bits=new int[32];
	int result=0;
	for (int i=0; i<32; i++){
	for(int j=0; j<A.length; j++){
	bits[i]+=A[j]>>i&1;
	bits[i]%=3;
	}
	result|=(bits[i]<<i);
	}
	return result;
	}
	}

view raw Single Number II.java hosted with ❤ by GitHub