C语言题目:只出现一次的两个数字

题目详情:给定一个arr数组,在这个数组里,有两个数字只出现了一次,其余数字均出现两次,请找出这两个数字,要求时间复杂度小于O(N),空间复杂度小于O(1)

首先我们应该思考如何才能准确的区分开这两个数字,假设这两个数字分别为x1,x2,既然其他元素数字都相同,那么我们完全可以将其它数字直接排除掉,这个时候我们需要用到异或操作符,即二进制下相同的两个数字异或为0.相异为1,符号为^

解题思路:首先我们可以将这数组中所有的元素进行异或,那我们得到的数字即两个不同的数字异或后的值,因为其他相同的值异或到一块后已为0,0和任何数异或都得任何数,假设得到的值为ret,这时需要将ret拆分为x1,x2,怎么拆分,,假设x1=5,x2=3这是x1,x2,ret的二进制位:

从图中可以看出,ret中二进制为1的位肯定是x1和x2分别为0,1的位,也就是说,只要我们知道它的哪一位是1,就可以区分x1,x2,最后再将区分开来的x1,x2分别放入不同的位置,就可以得到这两个数字

解题过程:第一步,得到ret,也就是x1,x1异或后的值

第二步:得到m,也就是ret哪一位为1

简单解释一下if语句里的内容,1向右移从0到32位正好对应三十二位二进制数,ret只要不为1,肯定有一位与1相按位与后得到1,1为真,即break;

第三步:拆分ret,得到x1,x2

 第四步,将x1,x2放到数组中,并返回

 完整代码如下:

#include
#include

int* get_two_one(int* arr,int numsize)
{
	int ret = 0;
	for (int i = 0; i < numsize; i++)
	{
		ret ^= arr[i];
	}
	int m = 0;
	while (m<32)
	{
		if (ret & (1 << m))
			break;

		++m;
	}
	int x1 = 0; int x2 = 0;
	for (int i = 0; i < numsize; i++)
	{
		if (arr[i] & (1 << m))
		{
			x1 ^= arr[i];
		}
		else
			x2 ^= arr[i];
	}
	int* retarray = (int*)malloc(sizeof(int)*2);
	retarray[0] = x1;
	retarray[1] = x2;
	return retarray;
}