数组中只出现一次的数字

题目描述

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

问题分析

可以利用异或的性质，如果存在两个只出现一次的数字，那么异或结果一定是两个不相同数字的异或结果。

• 这道题我们可以利用异或的特性--两个相同数字异或，结果为0。把数组中的数据全部想成二进制会更容易理解。

• 首先我们来考虑数组中只有一个出现一次的数字的情况，这种情况下，我们直接异或数组中的所有值即可得到这个数字；接下来考虑有两个出现一次的数字的情况，这种情况下，我们可以把原来的数组分成两组，每组里面各有一个只出现一次的数字，然后运用前面的解法即可得到结果。

• 问题的关键是如何划分成两个数组。我们呢可以根据全部值异或的结果进行思考，我们可以先把结果中最右边的1作为划分条件，然后判断数组中每个数字该位置上是不是1，如果是则为第一组，否则为第二组。这样分完之后，一组里面正好一个只出现一次的数字。

解题思路1

class Solution {
public:

    bool isBiteOne(int data,int index)
    {
        data = data >> index;
       return (data &1);
    }

    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if (data.size() <2)
        {
            return;
        }
        //异或计算
        int tmp = data[0];
        for(int i = 1; i < data.size(); ++i)
        {
            tmp = tmp ^ data[i];
        }
        if (tmp == 0)
        {
            return;
        }
        //记录最左边为1的位置
        int index = 0 ;
        while ((tmp & 1) == 0)
        {
            tmp = tmp >> 1 ;
            index++;
        }
        *num1=*num2=0;
        for(int i = 0; i < data.size(); ++i)
        {
            if (isBiteOne(data[i],index))
            {
                *num1 = *num1 ^ data[i];
            }
            else
            {
                *num2 = *num2 ^ data[i];
            }
        }

    }
};