32-有两个单独的数字,其它数字成对,请输出这两个单独的数字-蒲公英云

32-有两个单独的数字,其它数字成对,请输出这两个单独的数字

解题代码

#include<stdio.h>
//得到tmp二进制右数第一个1的值！！！
//100->4; 10101->1; 1010->2
int GetBit(int tmp)
{
    int i = 1;
    for(int j=0;j<32;j++)
    {
        if((tmp & i) != 0)
        {
            break;
        }
        i <<= 1;
    }
    return i;
}
//有两个单独的数字,其它数字成对,请输出这两个单独的数字
//分组:1.将两个单独数字分在不同组,2.相同数字一定在同一组
//分组的办法:异或的结果的二进制右数第一个1作为分组依据 
//右数的第一个1，说明这2个单独出现的数字在这个位上出现了不同，我们就可以分开了！
void Num2(int *arr,int len)//O(n),O(1)
{
    int tmp = 0;
    int x1 = 0; //第一个单独的数字
    int x2 = 0;//第二个单独的数字
    int flg = 0;//分组依据
    for(int i=0;i<len;i++)//计算异或的值
    {
        tmp ^= arr[i];
    }
    //得到tmp二进制右数第一个1的值
    flg = GetBit(tmp);
    for(int i=0;i<len;i++)
    {
        if((arr[i]&flg) == 0) //分为两组数据,分别^
        {
            x1 ^= arr[i];
        }
        else
        {
            x2 ^= arr[i];
        }
    }
    printf("%d,%d\n",x1,x2);
}
int main()
{
    int arr[] = {
    1,2,3,4,2,1,4,7};
    Num2(arr,sizeof(arr)/sizeof(arr[0]));
    return 0;
}