找出单身狗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;
}
有什么疑问可以私信哦,看完有收获的话动动小手点个赞吧!!!