Leetcode 题目解析之 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?

对于数组{1,1,1,2}来说，分析每一位：

0 0 0 1 
0 0 0 1 
0 0 0 1 
0 0 1 0 
…………… 
0 0 1 3 (位数)

可以分析，分别计算每一位1的出现次数n，如果n%3==1，那么结果中这一位就应该是1。

    public int singleNumber(int[] nums) {
        int rt = 0, bit = 1;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int v : nums) {
                if ((v & bit) != 0) {
                    count++;
                }
            }
            bit <<= 1;
            rt |= (count % 3) << i;
        }
        return rt;
    }