首页 > 代码库 > 找出数组中唯一的重复元素

找出数组中唯一的重复元素

【问题】

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。 每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?

【代码】

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*根据异或法的计算方式,每两个相异的数执行异或运算之后,结果为1;
每两个相同的数异或之后,结果为0,任何数与0异或,结果仍为自身。
所以数组a[N]中的N个数异或结果与1至N-1异或的结果再做异或,
得到的值即为所求。*/
int findRepeat1(int *a, int len)
{
	int i, res;
	res = a[0];
	for (i = 1; i < len; i++) {
		res ^= i;
		res ^= a[i];
	}
	return res;
}

/*利用下标与单元中所存储的内容之间的特殊关系,进行遍历访问单元,
一旦访问过的单元赋予一个标记,利用标记作为发现重复数字的关键。*/
int findRepeat2(int *a, int len)
{
	int index;
	index = a[len - 1] - 1;
	while (1) {
		if (a[index] < 0)
			break;
		a[index] *= -1;
		index = a[index] * (-1) - 1; 
	}
	return index + 1;
}

int main(void)
{
	int a[] = {1, 2, 3, 4, 5, 6, 4};
	int res;
	res = findRepeat2(a, 7);
	printf("%d\n", res);
	return 0;
}