找单身狗2

找单身狗2

之前遇到类似的题目的思路：

首先写出这些数的二进制形式：

核心原理

接下来的问题是怎么把5和6分开来？

这里是最后一位进行比较，按位异或是相同为0，相异为1，最后一位从上图看出是1，说明这两个数不一样，就可以让这两个数被分开

这道题的难点：

1.怎么把它分成两组？

2.为什么分成两组？

3.根据什么标准分成两组？

接下来是代码过程：

void FindNum(int arr[],int n,int* pNum1,int*pNum2)
{
    //1.对整个数组进行异或处理
    int tmp=0;
    for(int i=0;i<n;i++)
    {
        tmp^=arr[i];
	}
}
//2.tmp接受两个不同数字异或的结果
int pos=-1;
for(int i=0;i<32;i++)
{
    if(((tmp>>i)&1)==1)
    {
        pos=i;
        break;
	}
}
if(pos==-1)
{
    *pNum1=-1;
    *pNum2=-1;
    return;
}
for(int i=0;i<n;i++)
{
    if((arr[i]>>pos)&1==1)
    {
        *pNum1^=arr[i];
	}
    else
    {
        *pNum2^=arr[i];
	}
}
int main()
{
    int arr[]={1,2,3,4,5,1,2,3,4,6};
    int len=sizeof(arr)/sizeof(arr[0]);
    int ret1=0;
    int ret2=0;
    FindNum(arr,len,&ret1,&ret2);
    printf("%d %d",ret1,ret2);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

运行结果