在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
思路：
此题有三种方法来解。第一种是常规思路，即将数组进行排序，然后再遍历数组找出重复的数字,时间复杂度最快为O（nlogn）；第二种解法是用哈希数组来解，用一个长度为n的辅助数组，原数组中的值当做辅助数组中的下标，该下标存储原数组中该下标值出现的次数，当该值大于1时即找到重复的数字，时间复杂度为O（n）,空间复杂度为O(n)；第三种解法不增加辅助空间。如果没有重复的数字，那么值与下标值对应相等；如果值与下表不相等，而且与值对应的下标的值也不等与该下标，则将值交换到对应的下标处，比如a[ i ] = m,m != i, a[i] = a[m],a[m] = m; 如果值与下标不相等，而且值对应的下标与该值相等了，说明该值重复出现了，比如a[i] = m,m != i,而a[m] = m,此时m为重复出现的数；
方法二代码：
public static int duplicateNumber(int[] arr,int length,int[] duplication){ int result = 0; if(arr == null || length < 1) return result; int len = arr.length; int[] temp = new int[len]; //建立哈希数组来保存数字出现的次数 for(int i=0;i<len;++i){ temp[arr[i]] ++; if(temp[arr[i]] >1){ //时间复杂度为O（n）,空间复杂度为O（n） result = arr[i]; //找到出现次数大于一次的话退出循环，返回该数字 duplication[0] = arr[i]; break; } } return result; }方法三代码：
public static int duplicateNumber1(int[] arr,int length,int[] duplication){ int result = -1; if(arr == null || length < 1) return result; for(int i=0;i<arr.length;i++){ while(arr[i] != i){ //时间复杂度为(n),空间复杂度为O(1),相比上面的方法空间复杂度减小了 if(arr[i] == arr[arr[i]]){ result = arr[i]; duplication[0] = arr[i]; break; }else{ int temp = arr[i]; arr[i] = arr[temp] ; arr[temp] = temp; } } } return result; }
