56剑指OFFER之数组中只出现一次的数字

参考资料：

[0]代码参考高琥的回答：
https://www.nowcoder.com/profile/5097639/codeBookDetail?submissionId=14787564
[1]思路参考ridikuius的回答：
https://www.nowcoder.com/profile/5097639/codeBookDetail?submissionId=14787564
寻找普适性的解决方案

思路：

注意运算符的优先级，& 和==

关键词：

&(1<<index)

自己的答案：

void FindNumsAppearOnce(vector<int> data, int* num1, int *num2)
{
    int nResult = 0;
    for (int i = 0; i < data.size(); i++)
    {
        nResult ^= data[i];
    }
    int nIndex = 0;
    while ((nResult&(1 << nIndex)) == 0)
    {
        nIndex++;
    }
    *num1 = 0;
    *num2 = 0;
    for (int i = 0; i < data.size(); i++)
    {
        if ((data[i] & (1 << nIndex)) == 0)
            *num1 ^= data[i];
        else
            *num2 ^= data[i];
    }


}

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        
        //整体思路是：
        //初等级：如果该数字中就一个数出现一次，其他数出现两次，异或就可以得出
        //进阶：如何把这两个数给区分开呢？
        //将全部数据进行异或，找到异或的结果第一位为1的那一位，比如8,7以及其他相同的，两个相同的，按位异或是0，剩下8和7了 1000 和0111，
        //异或结果为1111,与1<<index按位与，所以index =0；这样我就能把8和7区分出来了。
        //
        //将数组分为2部分第一部分，那1位为0，按位与，结果是0，第二部分，那一位为1，按位与，结果是1
        //
        //记住按位与1<<index就行
        
        //步骤1：先所有数字进行按位异或，找到那一位，然后找按位与1<<index为0的第一个数，
        //步骤2：然后用按位与1<<index把两个数区分来
        
        int result=0;
        //步骤1：
        for(int i=0;i<data.size();i++)
        {
            result^=data[i];
        }
        //步骤2：
        int index =0;
        while((result&(1<<index)) == 0)
        {
            index++;
        }
        *num1 =0;
        *num2 =0; 
        for(int i=0;i<data.size();i++)
        {
            //比如把8和7区分开了
            if((data[i]&(1<<index))==0)
                *num1^=data[i];
            else
                *num2^=data[i];
        }
        
    }
};

标准答案：

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {

        /*
        //方法1：普适性的解决方案
        //步骤1：先数据从头到尾进行排序,
        sort(data.begin(),data.end());
        //步骤2：顺序遍历找到这个数
        vector<int> num;
        for(int i=1;i<data.size()-1;i++)
        {
            if(data[i] == data[i-1]||data[i] == data[i+1])
                continue;
            else
                num.push_back(data[i]);
        }
        if(data[0]!= data[1])
            num.push_back(data[0]);
        if(data[data.size()-1] != data[data.size()-2])
            num.push_back(data[data.size()-1]);
        *num1 = num[0];
        *num2 = num[1];
        */
        //第二种，取巧,按位异或的思路.过几天就忘了。
        
        int num = 0;
        for(int i=0;i<data.size();i++)
        {
            num ^=data[i];
        }
        
        int index =0;
            
        while((num&(1<<index))==0)
        {
            index++;
        }
        
        *num1 = 0;
        *num2 = 0;
        for(int i=0;i<data.size();i++)
        {
            if((data[i]&(1<<index))==0)  //!!!!!!!!!!!!要注意()!!!
                *num1 ^= data[i];
            else
                *num2 ^= data[i];
        }
        
        
    }
    
};