数组中只出现一次的数字

时间：2025-03-22 07:03:14

题目一：

一个整型数组里除了1个数字只出现一次之外，其他的数字都出现了两次。请写出程序找出这个只出现1次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

这个很简单，通过异或就可以除掉相同的数字，到最后只剩下一个只出现一次的数字。

参考代码如下：

void FindNumAppearOnce(int data[], int length, int *num)
{
	if(data == NULL || length < 1)
		return;

	int xorAll = 0;
	for(int i = 0; i < length; i++)
		xorAll ^= data[i];

	*num = xorAll;
}

题目二：

一个整型数组里除了2个数字只出现一次之外，其他的数字都出现了两次。请写出程序找出这个2个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

这个也是使用异或的思想。
既然有两个不同的数字num1、num2，那么这两个数字至少有一位不同，异或结果肯定至少有一位是1（其他数字成对出现不影响异或结果），也就是异或结果为1的地方就是这两个数字对应的位不同的地方。假如异或结果第k为是1，那么num1和num2的第k位一个为0，一个为1。我们根据第k为是否为0把它们异或到不同的结果xor1和xor2中。到最后xor1中和xor2中就保存的是num1和num2（或num2和num1）。

参考代码如下：

void FindNumsAppearOnce(int data[], int length, int *num1, int *num2)
{
	if(data == NULL || length < 2)
		return;

	int xorAll = 0;
	for(int i = 0; i < length; i++)
		xorAll ^= data[i];

	int k = 0;
	while((xorAll & (1 << k)) == 0) k++;

	int xor1 = 0, xor2 = 0;
	for(int i = 0; i < length; i++)
		if(data[i] & (1 << k))
			xor1 ^= data[i];
		else
			xor2 ^= data[i];

	*num1 = xor1;
	*num2 = xor2;
}

题目三：

一个整型数组里除了3个数字只出现一次之外，其他的数字都出现了两次。请写出程序找出这3个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

这个就稍微复杂一点，但是思想仍然相同。
由于所有数字的异或结果可能是0，因此，我们不能直接从所有数字异或的结果中获取信息。
3个不同的数字num1，num2，num3，那么他们至少有两位是不完全一样的，也就是存在两个位置，有一个是0另外两个是1或者有一个是1另外两个0。这里我们对每一位都进行分别保留异或结果。使用xor1[32]和xor2[32]，如果一个数的第k位为1就异或到xor1[k]中，如果第k位为0，就异或到xor2[k]中，同时我们记录第k位为1的数字的个数。
最后，对于xor1[k1]和xor2[k1]，xor1[k2]和xor2[k2]，会有这两个位置异或结果不为0。如果第k1个位置为1的数字的个数是奇数，那么xor1[k1]中就是一个只出现一次的数，我们设为num1，否则xor2[k1]中保存的是num1，同样k2位置xor1[k2]和xor2[k2]有一个是num2，num3也可以求出来了，所有数字异或然后再异或一次num1和num2，剩下的就是num3。

参考代码如下：

void FindNumsAppearOnce(int data[], int length, int *num1, int *num2,int *num3)
{
	if(data == NULL || length < 3)
		return;
	const int INT_BITS = sizeof(int)*8;
	int xor1[INT_BITS], xor2[INT_BITS], cnt1[INT_BITS];
	memset(xor1,0,sizeof(xor1));
	memset(xor2,0,sizeof(xor2));
	memset(cnt1,0,sizeof(INT_BITS));
	int i, k, xorAll = 0;
	for(i = 0; i < length; i++)
	{
		for(k = 0; k < INT_BITS; k++)
		{
			if(data[i] & (1 << k))
			{
				xor1[k] ^= data[i];
				cnt1[k]++;
			}
			else
				xor2[k] ^= data[i];
		}
		xorAll ^= data[i];
	}
	k = 0;
	while(k < INT_BITS)
	{
		if(xor1[k]  && xor2[k])
		{
			if(cnt1[k] & 1)
				*num1 = xor1[k]; 
			else
				*num1 = xor2[k]; 
			break;
		}
		k++;
	}
	k++;
	while(k < INT_BITS)
	{
		if(xor1[k]  && xor2[k])
		{
			if(cnt1[k] & 1)
				*num2 = xor1[k]; 
			else
				*num2 = xor2[k]; 
			break;
		}
		k++;
	}
	*num3 = xorAll ^ (*num1) ^ (*num2);
}

但是，此方法的空间复杂度并不是O（1），而是O（logINT_BITS）。我们要继续想办法。

请参考./blog/static/25411174201283084246412/


相关文章