寻找单身狗

题目要求

一个数组中，其余数字都出现两次，只有一个数字出现一次，求出这个
单独的数字（单身狗）
1
2

解题思路（查找一个单身狗）

思路一

可以从第一个数字开始，在整个数组中一一查找，若有没有相同的数字，则次数字便是单身狗；若不是，便查找下一个数字，直到查找到单独的数字为止。

思路二
利用异或的思想
若两个数字相同，则异或结果为0
若两个数字不同，则异或结果一定不为0
并且0与单身狗数字的异或结果还是单身狗本身

这里便采取思路二来解题，将整个数组进行异或处理。

代码实现如下

#include
void Find_single(int arr[], int sz, int* p)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
	    //结果直接由指针带回
		*p ^= arr[i];
	}
}
int main()
{
	int arr[] = { 1,2,3,1,2,3,4 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int dog = 0;
	Find_single(arr, sz, &dog);
	printf("单身狗为:>%d\n", dog);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

运行结果正确，并且证明了思路二的正确性

扩展

既然上面可以寻找一个单身狗，那两个，三个又该怎么办呢？

其实思路是大同小异的，下面就用相同的思路来寻找两个单身狗

既然是两个单身狗，那么异或的结果一定不会与其中一个单身狗的数值相同。所以便要考虑一个问题，异或结果数字中哪一位为1或者哪一位为0呢

整体思路如下

 1. 所有数字异或
 2. 找出异或结果数字哪一位为 1
 3. 以第n位为1，分一组；第n位为0分一组
1
2
3

代码实现如下

#include
void Find_single(int arr[], int sz, int* p1, int* p2)
{
	//1.异或
	int ret = 0;
	int i = 0;
	for (i == 0; i < sz; i++)
	{
		ret ^= arr[i];
	}

	//2.计算异或结果的数字二进制中哪一位是1
	int count = 0;
	for (count = 0; count < 32; count++)
	{
		if (((ret >> count) & 1) == 1)
		{
			break;
		}
	}
	//count记录异或结果数字二进制中右边第几位是1

	for (i = 0; i < sz; i++)
	{
		//以count位为1或者0，进行分组
		//第count位为1
		if (((arr[i] >> count) & 1) == 1)
		{
			*p1 ^= arr[i];
		}
		//第count位为0
		else
		{
			*p2 ^= arr[i];
		}
	}
}
int main()
{
	int arr[] = { 1,2,3,4,1,2,3,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int dog1 = 0;
	int dog2 = 0;
	Find_single(arr, sz, &dog1, &dog2);
	printf("单身狗为;>%d,%d", dog1, dog2);
	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
47

运行结果正确，同时也证明思路的正确性，所以依次类推便可以计算三个，四个，甚至更多单身狗。