1-1000这1000个数放在含有1002个元素的数组中，只有唯一的一个元素值重复，其他均只出现一次。每个数组元素只能访问一次，设计一个算法，将他找出来；不用辅助空间，能否设计一个算法实现。

异或法
设重复数字为A,其余N-2个数字异或为B，N个数字异或为A^B,前N-1个数字异或为A^A^B,由异或的性质可得（A^B)^(A^A^B)=A。所以代码如下： 
#include <stdio.h>
#include <stdlib.h>
#define random(x)(rand()%x)
#define N 1001
int arr[N];
int main()
{
	for (int i = 0; i < N-1; i++)
	{
		arr[i] = i + 1;
	}
	arr[N - 1] = random(1000)+1; //最后一个数是随机数
	int x = 0;
	//A^A^B
	for (int i = 0; i < N; i++)
	{
		x ^= arr[i];
	}
	//A^B
	for (int i = 0; i < N - 1; i++)
	{
		x ^= arr[i];
	}
	printf("%d\n", x);
	return 0;
}