在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。 请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
有一个很简便的方法，那就是遍历一次数组，把第一次碰到的数字放入一个set集合中，每次放入set集合的时候，先判断set集合中有没有这个数，如果有，就找到了一个重复的数字。
再题目描述中，很容易注意到，数组长度为n，所有数字的范围都在0~n-1内。如果没有重复的数字，那么排序后的数字i将会出现在下标为i的地方，但是由于有重复的数字，那么有些位置上的数会有重复。
基于此，现在可以从头扫描这个数组，当扫描到下标为 i 的数字时，先比较这个数字 m 和下标 i 是不是相等的，如果是相等的，就可以扫描下一个坐标上的数字；如果不相等，就把这个数 m 和下标为 m 上的数字进行比较，如果相等，就找到了一个重复的数字；如果不等，就交换这两个数字的位置，把 m 放到 m 的位置上，重复这么一个过程
public static boolean duplicate(int[] numbers,int length,int[] 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; } } for(int i = 0;i < length;i++){ while(numbers[i] != i){ if(numbers[i] == numbers[numbers[i]]){ duplication[0] = numbers[i]; return true; } //交换两个位置上的数 int temp = numbers[i]; numbers[i] = numbers[temp]; numbers[temp] = temp; } } return false; } //test public static void main(String[] args){ int length = 5; int[] numbers = {1,2,1,4,2}; int[] duplicate = new int[1]; System.out.println(duplicate(numbers,length,duplicate) + " : " + duplicate[0]); }