剑指offer刷题————数组中只出现一次的数字

问题重述：

题目：一个整型数组里面除了两个数字之外，其他的数组都只出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度为O(n),空间复杂度为O(1)。

例如：输入数组{2,4,3,6,3,2,5,5}

思路解析：

首先我们知道，两个相同的数字进行亦或操作的结果为0，而0与任何数组进行亦或操作的结果为原数。

那么，如果数组中只有一个只出现一次的数的话，我们遍历数组，进行亦或操作，即可得到结果。

吸取经验，我们继续将所有的数都进行亦或操作，由于数组中有两个只出现一次的数字，因此亦或的结果为这两个只出现一次的数进行亦或操作得到的值。

我们可以判断，这个数从左边数，第一次出现1的位置。假设这个数的第k位为1（且为最右边的1），那么两个只出现一次的数字中，肯定有一个数的第k位为1，而另一个数的第k位为0。

因此，我们可以根据第k位是否为1来将数组分为两组，分别进行亦或操作，就可以得到两个只出现一次的数了。

注意：由于其他数都是成双出现的，那么它们肯定会被分在固定的一组里面。

代码实现：

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.empty()||data.size()<2)
            return;
        int resultExclusiveOR = 0;
        for(auto e:data)
            resultExclusiveOR ^= e;
        int indexOf1 = 0;
        while((resultExclusiveOR&1)==0&&(indexOf1<8*sizeof(int)))
        {
            resultExclusiveOR = resultExclusiveOR>>1;
            ++indexOf1;
        }
        for(auto e:data)
        {
            if(isBit1(e, indexOf1))
                *num1 ^= e;
            else
                *num2 ^= e;
        }
    }
    bool isBit1(int num,int index)
    {
        return (num>>index)&1;
    }
};