[LintCode] 83 Single Number II 解题报告

Description
Given 3*n + 1 numbers, every numbers occurs triple times except one, find it.



Example
Given [1,1,2,3,3,3,2,2,4,1] return 4



Challenge
One-pass, constant extra space.



思路
如果把所有的数字以二进制的形式来看，那么如果一个数字出现了k次，那么这个数的二进制形式里所有出现1的位置，会出现k次。
我们可以想到，如果遍历数组，把所有数字的所有1的位置统计频率，那么最后只要把每个位置对k求模，就可以把重复k遍的数字都cancel out。



Code

public class Solution {
    /**
     * @param A : An integer array
     * @return : An integer 
     */
    public int singleNumberII(int[] A) {
        // write your code here
        
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int j = 0; j < A.length; j++) {
                if (((A[j] >> i) & 1) == 1) {
                    count++;
                }
            }
            result |= ((count % 3) << i);
        }
        
        return result;
    }
}