Single Number II解题报告

Description:

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?

Link:

https://leetcode.com/problems/single-number-ii/#/description

解题方法：

把数组中每个数作为2进制去处理，那么当把n个数作为2进制放到一起，可以找出规律，比如：

...000111000...
...001001000...
...000111000...
...000111000...

由此可以看出规律，当分别记录数组的所有数在每一位上的总和（即把每一位上的1以10进制的形式相加）只有3种情况：
1、3a+1
2、3b
3、0
所以只要把数组中的数的二进制每一位的1统计起来，然后再%3，就可以还原特定的那个数（知道特定的数在每一位上是否有1）。

Time Complexity：

O(N)

完整代码：

int singleNumber(vector<int>& nums) 
    {
        int sum, ans = 0;
        for(int i = 0; i < 32; i++)
        {
            sum = 0;
            for(auto a: nums)
            {
                if((a>>i) & 1)
                    sum++;
            }
            if(sum % 3)
                ans |= 1<<i;
        }
        return ans;
    }