[leetcode_137] Single Number II

给出 n 个数，里面每个数字重复 3 次，只有一个数字只出现一次，求该数字 [线性时间和空间]
相信两个数的大家都会，异或就行。
其实最开始用 map 过，觉得不符合题意，看了别人的思路，知道了，其实就是题目的变形，感觉不会举一反三，而且对问题的分析能力不够。
异或的目的就是计数每个位置出现 1 的个数，如果有两次就清零。
同理，3 个数我就出现 3 次清零。
附上代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
public:
    int singleNumber(int A[], int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int now = A[0];
        int one = now;
        int two = 0;
        int three = 0;
        for(int i = 1; i < n; i++)
        {
            int input = A[i];
            int in1 = one & input;
            one = one ^ input;
            int in2 = two & in1;
            two = two ^ in1;

            one = one ^ in2;
        }
        return one ^ two;
    }
};