题解 | #数组中只出现一次的数字#

这道题有一个前置题目，就是将本题的条件改为“一个整型数组里除了一个数字n之外，其他的数字都出现了两次”。

先来解决这道前置题目，可以想到用异或运算解决，出现两次的数字异或之后为0，而0^n = n，所以最后得到的数一定是n。

接下来解决本题。本题有两个数字只出现一次，所以依次异或一遍得到的是两个数字做异或的结果tmp。

我们考虑异或操作是一个位运算，当两个数字的同一位不同时，异或得到该位为1，否则为0。

所以，我们可以从tmp中选出为1的一位，然后将原数组分为两组，第一组为该位为1，第二组为该位为0，这样就能将两个只出现一次的数分到两个数组中，且这两个数组都满足“一个整型数组里除了一个数字n之外，其他的数字都出现了两次”。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int sum = 0;
        for (auto &i: data) sum ^= i;
        int bt = 0;
        while (((sum >> bt) & 1) == 0) bt++;
        int n1 = 0, n2 = 0;
        for (auto &i: data) {
            if ((i >> bt) & 1) {
                n1 ^= i;
            }
            else {
                n2 ^= i;
            }
        }
        *num1 = n1;
        *num2 = n2;
    }
};