【答案解析】问题描述：数组a[N]，1～N-1这N-1个数存放在a[N]中，其中某个数重复1次。写一个函数，找出被重复的数字。要求每个数组元素只能访问1次，并且不用辅助存储空间。
由于题目要求每个数组元素只能访问1次，且不用辅助存储空间，因此可以从原理上入手，采用数学求和法，因为只有一个数字重复1次，而又是连续的，根据累加和原理，对数组的所有项求和，然后减去1～N-1的和，即为所求的重复数。示例如下：
public class Test{
public static int xor_findDup(int[]a){
int n=a.length;
int tmp1=0;
int tmp2=0;
for(int i=0; i＜n-1; ++i){
tmp1+=(i+1);
tmp2+=a[i];
}
tmp2+=a[n-1];
int result=tmp2-tmp1;
return result;
}
public static void main(String[]args){
int a[]={1, 2, 1, 3, 4};
int missingNum=xor_findDup(a);
System.out.println(missingNum);
}
}
程序运行结果为：
1
如果题目没有要求每个数组元素只能访问1次，且不允许使用辅助存储空间，还可以用异或法和位图法来求解。
(1)异或法
根据异或法的计算方式，每两个相异的数执行异或运算之后，结果为1；每两个相同的数执行异或运算之后，结果为0，所以，数组a[N]中的N个数异或结果与1～N-1异或的结果再做异或运算，得到的值即为所求。
设重复数为A，其余N-2个数异或结果为B，N个数异或结果为A^A^B，1～N-1异或结果为A^B，由于异或满足交换律和结合律，且X^X=0，0^X=X，则有(A^B)^(A^A^B)=A^B^B=A。示例如下：
public class Test{
public static int xor_findDup(int[]a){
int n=a.length;
int i;
int result=0;
for(i=0; i＜n; i++){
result^=a[i];
}
for(i=1; i＜n; i++){
result^=i;
}
return result;
}
public static void main(String[]args){
int a[]={1, 2, 1, 3, 4}; int missingNum=xor_findDup(a);
System.out.println(missingNum);
}
}
程序运行结果为：
1
(2)空间换时间法
申请长度为N-1的整型数组flag并初始化为0，然后从头开始遍历数组a，取每个数组元素a[i]的值，将其对应的数组flag中的元素赋值为1，如果已经置过1，那么该数就是重复的数。示例如下：
public class Test{
public static int findInteger(int[]a){
int n=a.length;
boolean[]arrayflag=new boolean[n];
int i=1;
int result=Integer.MAX_VALUE;
while(i＜n){
arrayflag[i]=false;
i++;
}
for(i=0; i＜n; i++){
if(arrayflag[a[i]]==false)
arrayflag[a[i]]=true;
else{
result=a[i];
}
}
return result;
}
public staric void main(String[]args){
int a[]={1, 2, 1, 3, 4};
int missingNum=findInteger(a);
System.out.println(missingNum);
}
}
程序运行结果为：
1
这种方法的空间复杂度比较大，需要申请长度为N的整数数组。当然也可以通过使用位图的方法来降低空间复杂度，即不是用一个整型数字来表示元素是否出现过(0表示未出现，1表示出现过)，而是使用1bit来表示，因此需要申请数组的长度为N/32取上整。
此题可以进行一个变形：取值为[1，n-1]含n个元素的整数数组，至少存在一个重复数，即可能存在多个重复数，O(n)时间内找出其中任意一个重复数，例如，array[]={1，2，2，4，5，4}，则2和4均是重复元素。
方案一：位图法。使用大小为n的位图，记录每个元素是否已经出现过，一旦遇到一个已经出现过的元素，则直接将之输出。该方法的时间复杂度是O(n)，空间复杂度为O(n)。
方案二：数组排序法。先对数组进行计数排序，然后顺序扫描整个数组，一旦遇到一个已出现的元素，则直接将之输出。该方法的时间复杂度为O(n)，空间复杂度为O(n)。
以上提出的两种方案都需要额外的存储空间，能否不使用额外存储空间呢?答案是可以。于是想到了方案三：取反法。取反：去的基本思路如下：如果遍历到数组中的元素为i，那么把a[i]的值取反，如果i在数组中出现两次，那么a[i]会经过两次取反操作，a[i]的值跟原始的值相等，且为正数；如果i出现了1次，那么a[i]的值为原始值的相反数，且为负数，可以根据这个原理来实现。实现方法如下：将数组元素值作为索引，对于元素arry[i]，如果array[array[i]]大于0，那么设置array[array[i]]=-array[array[i]]；如果array[array[i]]小于0，那么设置array-[array[i]]=-array[-array[i]]，最后从数组第二个元素开始遍历数组，如果array[i]＞0，那么这个数就是重复的。由于在进行遍历后对数组中的数据进行了修改，因此需要对数据进行还原(对数组中的负数取反)。示例如下：
public class Test{
public static int xor_findDup(int[]a){
int n=a.length;
int result=Integer.MAX_VALUE;
for(int i=0; i＜n; i++){
if(a[i]＞0){
a[a[i]]=-a[a[i]];
}else{
a[-a[i]]=-a[-a[i]];
}
}
for(int i=1; i＜n; i++){
if(a[i]＞0)
result=i;
else
a[i]=-a[i];
}
return result;
}
public static void main(String[]args){
int a[]={4, 2, 1, 3, 4};
int missingNum=xor_findDup(a);
System.out.println(missingNum);
}
}
方法四是一种非常“诡异”的算法，就是采用类似于单链表是否存在环的问题。“判断单链表是否存在环”是一个非常经典的问题，同时单链表可以采用数组实现，此时每个元素值作为next指针指向下一个元素。本题可以转化为“已知一个单链表中存在环，找出环的入口点”这种想法。具体思路如下：将array[i]看作第i个元素的索引，即array[i]→array[array[i]]→array[array[array[i]]]→array[array[array[array[i]]]]→…，最终形成一个单链表，由于数组a中存在重复元素，因此一定存在一个环，且环的入口元素即为重复元素。
该题的关键在于，数组array的长度是n，而元素的范围是[1，n-1]，所以array[0]不会指向自己，进而不会陷入错误的自循环。如果元素的范围中包含0，那么该题不可直接采用该方法。示例如下：
public class Test1{
public static int findInteger(int a[]){
int x, y;
x=y=0;
do{
x=a[a[x]]; //x一次走两步
y=a[y]; //y一次走一步
}while(x!=y); //找到环中的一个点
x=0;
do{
x=a[x];
y=a[y];
}while(x!=y); //找到入口点
return x;
}
public static void main(String[]args){
int a[]={1, 2, 1, 3, 4};
int missingNum=findInteger(a);
System.out.println(missingNum);
}
}
程序运行结果为：
1