一、寻找一个单身狗🐶
1、题目描述
在一个整数数组中，有一个数只出现一次，别的数都出现两次，请找出只出现一次的数字。
2、思路分析
面对这样的问题， 可能首先想到的是对数组的元素进行遍历，记录每个元素出现的次数，然后找到只出现一次的数字，但是有一种更为巧妙的方法，就是对遍历数组元素并进行异或运算，异或运算有如下所示的性质，利用异或运算自反的性质就找到那个单身的数字。
3、代码实现
#include<stdio.h> void single_dog(int num[], int n) { int a = 0;//0与任何数异或为那个数本身 for (int i = 0; i < n; i++) { a ^= num[i]; } printf("单身狗为：%d", a); } int main() { int num[5] = { 2,1,2,1,4 }; single_dog(num, 5); }
运行结果：
二、寻找两个单身狗🐶🐶
1、题目描述
在一个整型数组中，有两个数只出现了一次，别的数都出现了两次 ，请找出这两个仅出现一次的数。
2、思路分析
这个问题如果继续采用上面直接遍历数组进行异或运算的话就只能得到这两个单身狗异或运算后的结果，那么我们可以换个角度思考，我们可以将这两个单身狗分别分到两个不同的组，然后对这两个组分别进行异或 来求，那么该怎么分组呢？
假设数组中的两个单身狗是4和5，那么我们对这两个数进行异或：
我们可以从位异或结果第一个为1的 位置进行分组，因为代表这两个数字在这一位必然是一个为0，另一个为1，然后将这两个数分到两个不同的数组中，然后再进行位异或就可以得到这两个单身的数字了。
3、代码实现
#niclude<stdio.h> void single_dog2(int num[], int n) { int a = 0;//0与任何数异或为那个数本身 int pos = 0; for (int i = 0; i < n; i++) { a ^= num[i]; } for (int i = 0; i < 32; i++) { if ((a >> i) & 1 == 1) { pos = i; break; } } int b = 0, c = 0; for (int i = 0; i < n; i++) { if ((num[i] >> pos) & 1 == 1) { b ^= num[i]; } else { c ^= num[i]; } } printf("两个单身狗为：%d %d\n", b, c); } int main() { int num[8] = { 2,4,2,1,4,5,5,6 }; single_dog2(num, 8); }
运行结果：
