题目描述
单身狗1
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
单身狗2
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
编写一个函数找出这两个只出现一次的数字。
例如：
有数组的元素是：1，2，3，4，5，1，2，3，4，6
只有5和6只出现1次，要找出5和6.
思路分析
这种题有两种思路，一种是暴力求解，遍历整个数组并对它们出现的次数进行计数，计数器为1的那个就是单身狗。这种思路比较简单粗暴，实现也比较简单，但是还有一种思路比它更加巧妙更加简单。
异或的思路：异或的根本思想是同0异1，且异或是支持交换律的，我们不用定义临时变量，通过异或就可以实现数据的交换。而当你将上面数组的元素一一异或，会发现，单独的那个数字被异或出来了，这就是一种简单的思路（基于异或的交换律）
找单身狗1
代码语言：javascript复制int find_single_dog1(int arr[], int sz)
{
int ret = 0;
for (int i = 0; i < sz; i )
{
ret ^= arr[i];
}
return ret;
}
int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
int ret = find_single_dog1(arr,sz);
printf("%dn", ret);
return 0;
}接下来是找单身狗2，在数组里找出两个单独出现的数字，这次是两个，那就不能简单的异或了，
基本的思路是将他们分组分为两个单身狗1一样的数组在进行异或，问题来了，如何分组呢？
将数组进行异或一下，你会得到5^6的结果，将它们而二进制来进行异或的话，所得到的值必然是有1个1的（其他结果也满足），接着我们取到它里面第几位1（右移与1异或），同时我们在数组里找到与它位置相同的，结果为1的值进行分类，并同时异或，这样就完成了分组，而分组异或的值就是两个单身狗。
代码语言：javascript复制void find_singledog2(int arr[], int sz,int* p1,int* p2)
{
int r = 0;
int pos = 0;
for (int i = 0; i < sz; i )
{
r ^= arr[i];
}
for (int i = 0; i < 32; i )
{
if ((r >> i) & 1 == 1)
{
pos = i;
break;
}
}
for (int i = 0; i < sz; i )
{
if ((arr[i] >> pos) & 1 == 1)
{
*p1 ^= arr[i];
}
else
{
*p2 ^= arr[i];
}
}
}
int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
int sz = sizeof(arr) / sizeof(arr[0]);
int s1 = 0;
int s2 = 0;
find_singledog2(arr,sz,&s1,&s2);
printf("%d %dn", s1, s2);
return 0;
}
