秒杀：只出现一次的数字系列

136. 只出现一次的数字
137. 只出现一次的数字 II

该方法能比较好的解决像此类问题：

给定一个数组，数组中只有一个元素出现1次，其余元素都出现k次，请找出出现1次的元素；

对于这类题，目前有三种方法可做，但各自有各自的特点分来看一下：

异或运算

该方法的局限性是如果k为奇数的话，该方法就不能使用了，原因很简单：1^1 = 0,1^1^1 = 1可见，当出现奇数次后全部异或后并没有将元素消除。但当k为偶数时，该方法就比较适用。

int value = 0;
vector<int> data;
for(int a : data){
	value ^= a;
}
cout << value << endl; // value就为数组中出现次数为1的那个数，其他元素出现了偶数次。
1
2
3
4
5
6

数学方法

去重思想，将原数组进行去重，然后求和，记为A;原数组不去重求和得B;然后使用(k * A - B)/(k - 1) = value；
该方法可以解决这类问题，但如果数字较大就会出现A,B越界情况。
代码如下：

vector<int> data;
set<int> data2(data.begin(), data.end());
int A = accumulate(data2.begin(), data2.end(), 0);
int B = accumulate(data.begin(), data.end(), 0);
int value = (k * A - B)/ (k - 1);
cout << value << endl;
1
2
3
4
5
6

位运算

利用数字每个位上得特征来进行计算。
因为如果1个数出现K次，那它对应的位上的1也就会出现k次，而那个出现1次的数上1就为位上所有1的个数对k取余。

int singleNumber(vector<int>& nums) {
        int k = 3, ans = 0;
        for(int i = 0; i < 32; ++i){
            int x = 1 << i, tmp = 0;
            for(int a : nums){
                if(x & a) tmp += 1;
            }
            tmp %= k;
            if(tmp == 1){
                ans += 1 << i;
            }
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

该方法可以解决此类问题，通吃。