剑指offer之找没有重复出现的数

系统管理员 2022-07-30 16:23 60阅读 0赞

## 一个数组中有两个数字只出现了一次，其他都是成对出现，找出这两个数字并输出？ ##

问题分析：如果要很好的解决找到两个不同的数字，我们先来看一个简单地例子:

如果只有一个数字出现了一次，其他都出现了两次，那仫我们利用异或的特性：“不同为1，相同为0”可以很容易的解决，就是用0与数组中每一个元素相异或得到不同的那个数字。

可是如果存在两个不同的数字应该如何找到他们呢？

以下先给出程序的测试代码：

int main()
    {
    	int sz=0;
    	int arr[10]={1,2,3,4,2,1};
    	sz=sizeof(arr)/sizeof(arr[0]);
    	differ_check(arr,sz);
    	system("pause");
    	return 0;
    }

我们是不是可以这样做呢？

.先用0来异或数组中的所有元素，得到那两个没有重复出现数字的异或结果，数组中重复出现的数字就为0了；

.既然两个数字没有重复出现那仫他们肯定是不同的，当然他们异或的结果肯定不是0，那仫我们是不是可以考虑利用这个异或的结果将这个数组中的元素分成俩个部分，这两个部分将没有重复出现的数字分到两个组里，并且在这两个组里分别异或数组中每个元素右移count（用来记录两个没有重复出现的数字异或结果1的位数）位来实现呢？当然是可以的啦！

.如何在没有重复出现数字异或结果里区别出那两个数字呢？

下面我们来看一个简单地例子：

1,2,3,4,2,1   3和4异或的结果是111，
    而3的二进制是011,4的二进制是100，
    可以发现这两个数字从左往右数第一位是不同的
    所以要区分这两个数字就要取出这个不同的位

我们就通过这个1将数组划分成两个部分，并记录这个1所在的位数，将数组中所有的元素都右移这个1所在的位数，再次把数组里的所有元素右移该位，在不同的部分异或找到没有重复出现的数字。

下面我们来看这个函数代码的实现部分：

void differ_check(int arr[],int sz)
    {
    	int i=0;
    	int a=0;
    	int b=0;
    	int ret=0;
    	int count=0;
    	for(i=0;i<sz;i++)   //找到两个没有重复出现数字的异或结果
    	{
    		ret^=arr[i];
    	}
    	while(!(ret&1))   //count记录1所在的位数
    	{
    		count++;
    		ret >>= 1;
    	}
    	for(i=0;i<sz;i++)  //将数组两个不同的位分成两组
    	{
    		if((arr[i] >> count)&1)
    		{
    			a^=arr[i];
    		}
    		else
    		{
    			b^=arr[i];
    		}
    	}
    	printf("%d %d没有匹配成功\n",a,b);
    }

以上实现中没有给出头文件，读者可自行添加；

通过上述例子使我更加深入的理解了异或的特性并且对位运算有了较好的把握，也理解了用位运算实现的小算法题。希望再接再厉。