找出单身狗2的代码实现
一、单身狗1代码回顾
1.1 题目
有一个数组只有一个数字出现一次，其余数字都是成对出现的
编写一个函数找出只出现一次的数字。
例如： 有数组的元素是：1 2 3 4 5 1 2 3 4
其中5只出现了1次，要找出数字5。
1.2 代码实现思路
之前我们学习过按位异或 ^ 这个操作符，它的运算方式是：对应的二进制位，相同为0，不同为1，
所以我们可以得到 n ^ n = 0 , 0 ^ n = n，因此，我们可以将数组中的元素全部异或，得到的就是唯一一个只出现一次的数字。
1.3 代码实现：
//单身狗1
int find_num(int arr[], int n)
{
int tmp = 0;
int i = 0;
for (i = 0; i < n; i++)
{
tmp ^= arr[i];
}
return tmp;
}
int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
int ret = find_num(arr,sz);
printf("%d\n", ret);
return 0;
}
二. 单身狗2
2.1题目
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
编写一个函数找出这两个只出现一次的数字。
例如：
有数组的元素是：1，2，3，4，5，1，2，3，4，6 只有5和6只出现1次，要找出5和6.
2.2 代码实现的大思路
根据各个数字二进制形式第一位数字进行分组，二进制位为0的分为一组，二进制位为1的分为一组，，将数组中的数字进行分组，分组之后再分别进行组内的异或 ，得到的就是只出现一次的数字 5 和 6 ，见下图
分组方式：
2.3 分组的具体步骤
- 将数组中的数字全部异或，得到的就是5^6的结果，结果是0011，有两个对应位不同，说明按照这两位的任意一位都可以将5和6分开，这里按第一位进行分组
- 将数组中的数字依次进行右移，右移之后和1进行按位与&计算，按照第一个位置得出的结果为0或者1进行分组
- 分组好之后进行组内的异或，得到的就是数组中只出现了一次的两个数字
见下图，便于理解：
2.4 代码的实现
//单身狗2
void FindNum(int arr[], int n, int* pNum1, int* pNum2)
{
//1.整体异或,异或的结果就是5^6的结果
int tmp = 0;
for (int i = 0; i < n; i++)
{
tmp ^= arr[i];
}
//2. 判断tmp哪一位是1
int pos = -1;//判断是那个位置
for (int i = 0; i < 32; i++)
{
if (((tmp >> i) & 1) == 1)
{
pos = i;//在第i位
break;
}
}
if (pos == -1)//如果没有为1的位
{
*pNum1 = -1;
*pNum2 = -1;
return;
}
for (int i = 0; i < n; i++)
{
if (((arr[i] >> pos) & 1) == 1)//右移pos位判断是否为1
{
*pNum1 ^= arr[i];
}
else
{
*pNum2 ^= arr[i];
}
}
}
int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
int len = sizeof(arr) / sizeof(arr[0]);
int ret1 = 0;
int ret2 = 0;
FindNum(arr, len, &ret1, &ret2);
printf("%d %d\n", ret1, ret2);
return 0;
}
有什么疑问可以私信哦，看完有收获的话动动小手点个赞吧！！！
