关于单身狗问题
路遥知马力，日久见人心。——元《争报恩》
1、题目
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。 编写一个函数找出这两个只出现一次的数字 例如： 有数组的元素是：1，2，3，4，5，1，2，3，4，6 只有5和6只出现1次，要找出5和6
2、方法
2、1方法一
因为有10个数字，那么可以根据最简单的方法，通过10回的依次排比，对比，从而得出结果。但是，其实仔细想一下还是可以明白，这种方法只不过是次数的堆积，感觉其实这种代码是很冗杂的。就例如下面的这段代码
int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
int i = 0;
int sz = sizeof(arr) / sizeof(arr[0]);
for (i = 0; i < sz; i++)
{
int flag = 0;
int j = 0;
for (j = 0; j < sz; j++)
{
if (i!=j&&arr[i] == arr[j])
flag = 1;
}
if (flag == 0)
{
printf("%d\n", arr[i]);
}
}
return 0;
}其实，这种方法最简单的，稍微理解一下，就可以了，但是，我们不知有这一种方法，我们还有一种不接“地府”方法，（反正我第一次看到并且理解完了后，感觉很舒服）
2、2方法二
其实回想一下，我对于操作符来说，还是不够熟悉，所以下面，我要夹带私货，重新温习一下位操作符
2、2、1私货
三种操作符：&（按位与），|（按位或），^（按位异或）。 注意：三种操作符的操作数，都必须为整数。 规则：1、&(按位与）*在整数二进制的情况下，两个数中有0则为0，同1，才为1。 2、|（按位或），两个数中，有1则为1，同0才为0. 3、**^（按位异或）**相同则为0，不同则为1
所以真正的方法二，从现在可以开始了，因为在前面的学习之中，我们可以知道三种操作符的玩法，这里我们可以借助，按位异或的操作符来帮助我们完成题目要求。就例如如下代码
void find(int* arr, int len, int* pnum1, int* pnum2)
{
int ret = 0;
for (int i = 0; i < len; i++)
{
ret ^= arr[i];
}
int pos = -1;
for (int i = 0; i < 32; i++)
{
if ((ret & 1) == 1)
{
pos = i;
break;
}
}
for (int i = 0; i < len; i++)
{
if ((arr[i] >> pos)&1)
{
*pnum1 ^= arr[i];
}
else
{
*pnum2 ^= arr[i];
}
}
}
int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
int ret1 = 0;
int ret2 = 0;
int sz = sizeof(arr) / sizeof(arr[0]);
find(arr, sz, &ret1, &ret2);
printf("%d %d", ret1, ret2);
return 0;
}这也是可以完成的，不过，还是要抓住，通过整个数组的按位异或的操作符，最后只会表现的结果是两个单身狗的异或结果，所以根据这样的结论，我们可以来把数组分为两组，不同的组里面再来异或，并且分别存入两个地址中，这样，只出现一次的数字就会分开，并且展示出来。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-09-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录