查找数组中只出现一次的数字

---

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写出这两个只出现一次的数字。

解题思路

查找数组中只出现一次的树字，一般有以下几种方法

• 通过两次完全遍历找到，只出现一次的数字。时间复杂度为 O(n^2).

• 通过Hash表 map<int,int> 在遍历的过程中，统计树字出现的次数。时间复杂度为 O(n), 但是空间复杂度不是 O(1).

• 通过异或的方法来判断。由于题中提到，其它的数字都出现两次，只有两个数字只出现一次，根据异或的定义：当两个数字相同时，返回 0 ，不同返回 1。 当数组中出现两次的数字异或完后，会变为 0.只剩下只出现一次的 数字。

  • 只有一个只出现一次的数字时，例如： {2,3,2}

    2的二进制为 0010， 3的二进制为 0011，0010 ^ 0011 = 0001, 然后将 0001 与 0010 异或 ：0001 ^ 0010 = 0011, 得到的结果是 3的二进制。也就说明，这个数组中，3是出现一次的数字。

  • 有两个只出现一次的数字时，例如: {2,4,3,6,3,2,5,5} 其中 4， 6只出现一次。但是就不能简单的异或处理了。所以要使用以下解决办法：

    • 首先，将数组的所有元素异或操作完后，判断得到结果二进制表示中第一个 1的位置 n；
    • 然后根据第 n位为 1的标准将数组分为两个子数组；
    • 对子数组进行异或操作，得到只出现一次的数字；

class Solution
{
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2)
    {
        int length = data.size();
        if (length < 2)
            return;
        
        int OrIndex = 0; // 数组异或操作的结果
        for (int i = 0; i < length; i++)
        {
            OrIndex ^= data[i];
        }
        
        unsigned int firstBit = FirstBitOf1(OrIndex); // OrIndex二进制表示中 1 第一次出现的位置
        
        *num1 = *num2 = 0;
        for (int j = 0; j < length; j++)
        {
            // 通过第n位是否为 1 将原数组分为两个子数组，并进行异或操作
            if (IsbitOf1(data[j], firstBit)) 
            {
                *num1 ^= data[j];
            }
            else
            {
                *num2 ^= data[j];
            }
        }
    }
    
    // 找到原数组异或操作后二进制中第一个 1 的位置
    int FirstBitOf1(int num)
    {
        unsigned int index = 0;
        // 在一个字节中寻找
        while ((num & 1) == 0 && (index < 8 * sizeof(unsigned int)))
        {
            num = num >> 1;
            index++;
        }
        return index;
    }
    
    // 判断一个二进制数字是否第 n 位为 1 
    bool IsbitOf1(int num, unsigned int index)
    {
        num = num >> index;
        return (num & 1);
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_40.html