💛找（一只或者多只）单身狗题目💛
作业标题
找单身狗
作业内容
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
编写一个函数找出这两个只出现一次的数字。
例如：
有数组的元素是：1，2，3，4，5，1，2，3，4，6
只有5和6只出现1次，要找出5和6.
💪 解题思路的分享💪 （一只单身狗）
我们需要用到 ^，也就是异或操作符。
“ ^ ”的异或指的是二进制中，对应的对应二进制位相同时异或为零，相异时异或为一
我们知道，大小相同的数字异或结果一定为0，而0与任何数字进行异或大小不会改变。
那么当单身狗只有一个时，我们可以直接让所有的数据异或在一起，这样最后得出来的就一定是那只单身狗了。
😊题目源码的分享😊
我们来看下面的例子。
#include<stdio.h> void Single_Dog(int *a, int sz,int *x) { for (int i = 0; i < sz; i++) { *x ^= a[i]; } } int main() { int x = 0; int a[] = { 1,1,2,2,3,3,4,4,5 }; int sz = sizeof(a) / sizeof(a[0]); Single_Dog(a, sz, &x); printf("单身狗是%d",x); return 0; }
运行结果如下：
成功找出单身狗5！
💪 解题思路的分享💪 （多只单身狗）
上面是只有一只单身狗的情况，如果单身狗有两只该怎么办呢？
首先，我们肯定是不能把它们一股脑地异或到一起了，因为单身狗们大小既不相等也大概率不为0，肯定是找不出来的。
不过我们知道，最后异或出来的结果肯定不为0，因为单身狗们的大小肯定不相等。
那我们就找到了解题思路——通过将两只单身狗分组来达到上面只有一只单身狗的情况，然后分别异或到一起。
分组的方法就可以按照异或的结果来，异或相同位0，相异为1，我们就可以找第一个不相等的位置来将单身狗分组，也就是异或结果二进制位里面第一个为1的位置，记录下这个位置。
之后再定义两个变量用来作为两只单身狗，初始化为0。
紧接着遍历数组，当所遍历到的数据右移上面所保存的位置和1按位与的结果为1时，就将它与x异或，反之就和y异或。
这样一通操作下来，x和y就变成了单身狗的样子了！
😊题目源码的分享😊
#include<stdio.h> void Single_Dog(int* a,int sz,int *m,int *n) { int i, pos = 0, ret = 0; for (i = 0; i < sz; i++) { ret^= a[i]; } for (i = 0; i < 32; i++) { if (ret >> i == 1) { pos = i; break; } } for (i = 0; i < sz; i++) { if ((a[i]>>pos&1) == 0) { *m ^= a[i]; } else if ((a[i] >> pos&1) == 1) { *n ^= a[i]; } } } int main() { int a[] = { 1,1,2,2,3,3,4,4,5,5,6,6,7,8 }; int sz = sizeof(a) / sizeof(a[0]); int m = 0, n = 0; Single_Dog(a, sz, &m, &n); printf("%d %d", m, n); return 0; }
👉 本菜鸡&总结 👈
这篇博客旨在总结我自己阶段性的学习，要是能帮助到大家，那可真是三生有幸！😀如果觉得我写的不错的话还请点个赞和关注哦~我会持续输出编程的知识的！🌞🌞🌞
这道题目的方法很难想到，实在不行的话咱们也可以直接采取暴力方式
也就是先排序，在经过一系列操作找出单身狗，不过这个方法有点太复杂了。
