找单身狗1

一个数组中只有1个数字出现1次，其他数字都是成对出现，找出这个单身狗。

对于这个问题，这里提供两种思路:

1.暴力求解

这种方法是最容易想到的，分别统计每个元素出现的次数，找到出现一次的那个数字即可。然而毕竟是暴力求解，这种求解方式的时间复杂度必然很高。相信大家能够写出暴力求解的代码，这里就不给出这种方法的代码了~

2.优雅解法

这种方法利用了异或的特点：相同为0，相异为1。a^a=0，a^0=a。另外，异或是支持交换律的，即3^5^3==3^3^5==5（大家不明白的话，可以写成二进制异或一下，就会豁然开朗，直接记住结论也行），那么我们可以利用异或的特点，将数组中每一个元素逐个异或到同一个数0上，那么最终异或的结果就是单身狗了。

代码如下：

#include <stdio.h>
int find_single_dog1(int arr[],int sz)
{
	int n = 0;
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		n ^= arr[i];//异或到n上
	}
	return n;
}
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("单身狗是%d\n", ret);
	return 0;
}

这道题让我们更加理解了异或的特点，挺好的！