这个题目的特点是数组a[n]中所有的数字都在[0,n)内。书上的方法是基于交换的O(n)时间复杂度，但是会改变原数组的内容。 这种解法可以举一个形象的例子：火车上查票。查到某一个座位i时，如果当前坐的这个人的票与座位号不符，那么就让他坐到他应该坐的位置上去。如果他的位置上已经坐的人的票与座位号也相同，那这么个座位的票就是重复出售了的，因为不可能同时有两个人要坐同一个位置。如果这个人的票与座位号不同，也就是说这个人也坐错了位置，那么先让他坐到i，同时继续判断。
public boolean duplicate(int numbers[],int length,int [] duplication) { int temp; if(length<=1) return false; for(int i=0;i<length;i++) { while(numbers[i]!=i) { if(numbers[numbers[i]]!=numbers[i]) { temp=numbers[numbers[i]]; numbers[numbers[i]]=numbers[i]; numbers[i]=temp; } else { duplication[0]=numbers[i]; return true; } } } return false; }下面的这个方法也是O(n)时间复杂度，也会修改原数组，但是它可以找出所有重复的数字，并且可以还原数组。
public static boolean duplicate(int numbers[],int length,List<Integer> duplication) { if(numbers==null||length<=0) return false; for(int i=0;i<length;i++){ if(numbers[i]<0||numbers[i]>length-1) { return false; } } boolean dup=false; for(int i=0;i<length;i++){ int index=numbers[i]; if(index>=length) index -=length; if(numbers[index]>=length) { duplication.add(index); dup=true; } numbers[index] +=length; } //还原数组 for(int i=0;i<length;i++){ numbers[i] %=length; } if(!dup) duplication.add(-1); return dup; }