数组中只出现一次的数字---剑指offer

数组中只出现一次的数字

C++，位运算，按位异或和按位与。

首先就是要知道，一个数a和初始为0的数b一次异或(b = a ^ b)，会得到b = a，两次异或，则b = 0。所以如果一个序列中，只有一个元素a出现次数为奇数，其他序列出现次数为偶数，将数b = 0与序列中所有值进行异或运算，则最终b = a。

这道题中给的序列中有两个出现了一次的元素a、b，其他都出现了两次。我们可以把这个序列分成两个子序列，每个子序列中包含一个出现一次的元素a和，其他都是出现了2次，这样分别异或运算就能得到答案了。

如何给序列分割呢？

• 首先定义一个变量a_b = 0，与序列中所有元素都进行异或^运算；
• 最后得到的a_b一定是等于a ^ b；
• 然后再找到a_b的二进制中第一个为1的位，假设这个位为i，这个位对于整个序列具有如下特点：
  • 如果a的i位为1，则b的i为一定为0，反之也成立，因为这个1是a和b异或的结果；
  • 相同的数的i位一定是相同的；
• 基于上述特点，可以用按位与将序列分成两个子序列，且这两个子序列中一定是符合“只有一个元素出现了1次，其他元素都出现了2次”的特征。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int a_b = 0;
        for (int &it : data) a_b ^= it;
        int i = 1;
        for (; !(i & a_b); i <<= 1) ;
        vector<int> v1, v2;
        for (int &it : data) {
            if (i & it)
                v1.push_back(it);
            else
                v2.push_back(it);
        }
        a_b = 0;
        for (int &it : v1) a_b ^= it;
        *num1 = a_b;
        a_b = 0;
        for (int &it : v2) a_b ^= it;
        *num2 = a_b;
    }
};