题目:一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。
我们直接看代码以及注释:
#include <stdio.h>
void Find(int* p,int n,int* pnum1,int* pnum2)
{
int i = 0;
int pos = 0;
int sum = 0;
//前面相同的数异或结果为0,最后将这两个数异或,得到sum
for (i = 0; i < n; i++)
{
sum ^= p[i];
}
for (i = 0; i < 32; i++)
{
//找到这两个不同的数异或后的结果按位与1,找到第一次1出现的位置,就记录这个1的位置,赋给pos,然后在原数组按照这个1的位置划分为两组,
//这两个不同的数一定会被分到两个不同的组,
//因为前面sum是这两个不同的数异或的结果,
//那么它们的二进制在某一位上肯定不一样,
//这个位置就是它们异或结果为1的位置,
//所以我们要找到它们异或结果第一次为1的位置;
//这里用sum按位与1,为0则将1左移,继续找,直到按位与的结果为1,我们就找到了这个位置;
if (sum & 1 << i)
{
pos = i;
break;
}
}
//按照上面我们找到那个位置,我们利用这个位置的不同(0和1)划分为两组,这两个数一定被分到两个不同的组,而且有相同的数的也会被分到同一组
//利用异或的特性,相同的数异或得到0,0再异或那个单独的数,就可以得到那一个不同的数;
//而两组都这样的话,就能找到这两个不同的数;
//最后通过地址改变主函数局部变量x和y的值,就能得到这两个数;
for (i = 0; i < n; i++)
{
if (p[i] & 1 << pos)
{
*pnum1 ^= p[i];
}
else
{
*pnum2 ^= p[i];
}
}
}
int main()
{
int arr[6] = { 1,2,1,2,3,5 };
//创建两个变量,假设为这两个不同的值,传地址进函数,最后通过地址改变值,从而从函数中得到这两个不同的值
int x = 0;
int y = 0;
Find(arr, 6, &x, &y);
printf("%d %d\n", x, y);
return 0;
}
例如: