[数据结构与算法]找出一个数组中出现了一次的数字（算法优化版）

这种题目直接写得话其实不难，很多同学都能立马想到用循环嵌套的方式来求。但是这种算法终究还是比较矬的（因为当你前面找的那个数已经出现了两次，你已经知道这个数不是单身汉了，可是当外层循环再次走到那个数时还是会进去无效地逐一对比一次，导致了程序运行时间和精简程度一般），并且它的时间复杂度高达O（n^2）不满足有些题目的限制，所以这个方法在这就不多赘述了

只求一个单身汉时

即一个数组里有一个数字只出现了一次，需要你找出来

哈希表遍历法

创建一个长度至少比目标数组数据范围大小大1的哈希数组(要使目标数组每个值都能对应到哈希数组的下标，下标是比数组长度少一位的)，然后遍历一遍目标数组，将其与哈希数组下标进行对比，如果相等就使哈希下标对应的数据++（所以一开始要将哈希数组初始化为一个值），之后再遍历一遍哈希数组判断值即可

int main()
{
int arr[7]={1,2,5,3,1,3,2}; //目标数组此时单身汉为5
int sz=sizeof(arr)/sizeof(arr[0]);
int arr1[6]={0}；    //创建哈希数组同时初始化所有元素为0
for(int i;i<sz;i++)
{
 arr1[arr[i]]++; //使目的数组对应到哈希数组的下标，匹配了就使哈希数组下标对应的值++
}
for(int i=0;i<6;i++)
{
 if(arr1[i]==1)   //因为刚开始我们将所有元素初始化为了0，如果值依然为0就代表目的数组没有这个数（所以不能直接用是否为2来判断是否为单身汉），为1则代表有这个数但是只出现了一次，	为2则代表原数组的这个数出现了两次。
  {
   printf("单身汉为：%d\n",i);
   exit(1) //找到了，就提前正常结束程序
  }
}

return 0;
}

这个算法时间复杂度为O（n）明显是好于嵌套循环的

异或

首先了解一下按位异或操作符。异或是针对二进制位操作的操作符，如果二进制位上的数相同则为0，相异则为1 有两个常用性质
1.0异或任何数等于任何数
2.相同的数异或结果为0，且不在乎次序。如：6 ^ 8 ^ 6=6 ^ 6 ^8=8,因为6 ^ 6是等于0的

上代码

int arr[7]={1,2,2,1,5}; //需要被查找单身汉的目标数组，单身汉为5
int a=0;
int sz = sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<sz;i++)
{
 a^=arr[i];    //根据上面的性质，a异或完所有数后剩下的值就是那个单身汉了
}
printf("%d\n",a);  

（进阶）找两个单身汉时

//思路
//1.先异或所有数一遍得到两个单身狗的异或值
//2.再找出比特值为1的位置，并记录下（因为异或是相异为1，这就代表这两个单身汉的在这个比特位的值是不一样的，所以用这一位上的1来遍历一遍目标数组的数就可以将两个单身汉分到两组分别寻找减少循环体度）
//3.循环所有数一遍，用移位操作符在记录的位置上按位与1，得到结果1或0的两组；在两个情况中分别定义两个变量一直按位与等于符合条件进去的值
//4.等循环结束两个变量的值就是两个单身汉了
void Search(int* arr,int sz)
{
	int a = 0;
	int pos = 0;     //记录比特位为1的位置，其实取随便一位都行
	for (int i = 0; i < sz; i++)
	{
		a ^= arr[i];
	}
	int b = a, c = a;   //新定义两个变量，同时赋值为0
	for (int i = 0; i < 32; i++)  //因为整型数是32个比特位
	{
		if ((a >> i) & 1)   //按位且上1，这样如果第一位比特位是1就为真进入程序，否则就继续循环然后用右移操作符判断下一位比特位
			pos = i;   //记录1是在第几位，即是将原数右移了多少次才找到的
	}
	for (int i = 0; i < sz; i++)
	{
		if ((arr[i] >> pos) & 1)  //遍历所有数，且将其用右移操作符移动pos位，判断这一位上是0还是1，分成两组来分别找出
			b ^= arr[i];
    	else
			c ^= arr[i];
	}
	printf("%d\n", b);  //当遍历完两种情况后b和c分别剩下的值自然就是两个单身汉了
	printf("%d\n", c);
}

int main()
{
	int arr[20] = { 1,2,2,3,4,6,6,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Search(arr,sz);
	return 0;
}

好啦好啦讲完了，友友们觉得有用的话可以收藏起来噢