137. Single Number II

题目分析

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
思路参考

代码

public class Solution {
    public int singleNumber(int[] A) {
        // 32 位数
        int[] temp = new int[32];
        
        for(int i = 0; i < A.length; i++) {
            for(int j = 0; j < 32; j++) {
                // 以下两步合起来就是取出最低位的值
                // 整个循环就是数不停的右移，然后不停的取出最低位的值
                int rotated = A[i] >> j;
                temp[j] += (rotated & 1);
            }
        }
        int res = 0;
        for(int i = 0; i < 32; i++) {
            temp[i] = temp[i] % 3;
            res += (temp[i] << i);
        }
        return res;
    }
}