题目要求
一个数组中，其余数字都出现两次，只有一个数字出现一次，求出这个 单独的数字（单身狗）
解题思路（查找一个单身狗）
思路一
可以从第一个数字开始，在整个数组中一一查找，若有没有相同的数字，则次数字便是单身狗；若不是，便查找下一个数字，直到查找到单独的数字为止。
思路二
利用异或的思想
若两个数字相同，则异或结果为0
若两个数字不同，则异或结果一定不为0
并且0与单身狗数字的异或结果还是单身狗本身
这里便采取思路二来解题，将整个数组进行异或处理。
代码实现如下
#include<stdio.h> 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或者哪一位为0呢
整体思路如下
1. 所有数字异或 2. 找出异或结果数字哪一位为 1 3. 以第n位为1，分一组；第n位为0分一组
代码实现如下
#include<stdio.h> 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; }
运行结果正确，同时也证明思路的正确性，所以依次类推便可以计算三个，四个，甚至更多单身狗。
