【C实现算法00】一个数组中除一个（两个）数只出现一次外其它数字都出现了两次，找出这个数，编程实现。

130 阅读 0 评论 86 点赞

我是靠谱客的博主调皮太阳，最近开发中收集的这篇文章主要介绍【C实现算法00】一个数组中除一个（两个）数只出现一次外其它数字都出现了两次，找出这个数，编程实现。，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题1：一个数组中除一个数只出现一次外其它数字都出现了两次，找出这个数，编程实现。

分析：当写出数组中每个元素的二进制序列时，很明显除了要找的数Num的二进制序列外其它序列都是成对出现的。我们知道两个完全相同的二进制序列异或（^）以后是0，所以在这里首先将0赋给Num（语句：Num = 0;），然后将数组的每个元素与Num进行异或操作，最终累计后Num的值就是要找的数。代码实现如下：

int FindNum(int a[],size_t n)
{
	int Num = 0;
	for (size_t i = 0; i < n;++i)
	{
		Num^= a[i];
	}

	return Num;
}

问题2：一个数组中除两个数只出现一次外其它数字都出现了两次，找出这个数，编程实现。

分析：显然这个问题是上面问题的扩展或升级，所以这里通过处理将它转化成上面问题是一个很不错的思路。我们定义一个变量ret并将其初始化为0,经过下面这个循环

int ret = 0;
for (size_t i = 0; i < n;++i)
{
        ret ^= a[i];
}

得到的ret实质上是要找的Num1与Num2异或的结果，因Num1与Num2是不同的两个数，所以ret的二进制序列中至少有一个位置是1，Num1与Num2的二进制序列在这个位置的特点是一个为1另一个为0。我们定义一个变量pos并将其初始化为0(这里规定二进制序列右边起第一个位置用0标记，以此类推),经过下面这个循环后

        int pos = 0;
	while (1)
	{
		if ((ret>>pos) & 1 == 1)
			break;

		++pos;
	}

pos标记的位置是ret的二进制序列从右起第一次出现1的那个位置。其实数组中部分元素的二进制序列在pos位置是1，部分元素的二进制序列在pos位置是0。到这里你仔细想，我们把数组中二进制序列在pos位置是1放到一起后这组数据的特点正是问题一所描述的那样，即就是除了一个数字外其他数字都是成对出现的，这里所指的“一个数字”真是我们要找的其中之一；再把数组中二进制序列在pos位置是0的放到一起也是同样的。利用这个思想具体找Num1与Num2的局部代码如下：

        for (size_t i = 0; i < n; ++i)
	{
		if ((a[i]>>pos)&1 == 1)
			Ret.Num1 ^= a[i];

		else
			Ret.Num2 ^= a[i];
	}

整个问题的代码实现如下（具体实现用了一个结构体，完全是为了函数返回时更方便整齐）：


typedef struct NUM
{
	int Num1;
	int Num2;
};

struct NUM FindTwoNum(int a[], size_t n)
{
	struct NUM Ret;
	Ret.Num1 = 0;
	Ret.Num2 = 0;

	int ret = 0;
	for (size_t i = 0; i < n;++i)
	{
		ret ^= a[i];
	}

	int pos = 0;
	while (1)
	{
		if ((ret>>pos) & 1 == 1)
			break;

		++pos;
	}

	for (size_t i = 0; i < n; ++i)
	{
		if ((a[i]>>pos)&1 == 1)
			Ret.Num1 ^= a[i];

		else
			Ret.Num2 ^= a[i];
	}

	return Ret;
}