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?

Solution1: HashMap

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

Solution2:

public class Solution {
    public int singleNumber(int[] A) {
        if( A.length == 1 ) return A[0];
        
        Arrays.sort(A);
        for( int i = 0 ; i + 2 < A.length; i = i + 3){
            if(A[i] == A[i+1] && A[i] == A[i+2]){
                continue;
            }else if( A[i] != A[i+1] ) return A[i];
        }
        
        return A[A.length - 1];
    }
}

Solution3: bit manipulation 
统计整数的每一位来得到出现次数。如果每个元素重复出现三次，那么每一位出现1的次数也会是3的倍数。统计完成后对每一位进行取余3，那么结果中就只剩下那个出现一次的元素。
只需要对数组进行一次线性扫描，统计完之后每一位进行取余3并且将位数字赋给结果整数，这是一个常量操作（因为整数的位数是固定32位），所以时间复杂度是O(n)， constant space。

public class Solution {
    public int singleNumber(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        
        int[] digits = new int[32];
        for(int i = 0; i < 32; i++) {
            for(int j = 0; j < A.length; j++) {
                digits[i] += (A[j] >> i) & 1;
            }
        }
        
        int res = 0;
        for(int i = 0; i < 32; i++) {
            res += (digits[i] % 3) << i;
        }
        return res;
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/22645599