题目描述
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中的某些数字是重复的，但不知道几个重复了，也不知道重复了几次。请找出数组中任意一个重复的数字。例如输入数组为{2,3,1,0,2,3,5}，那么对应的输出是重复的数字2或者3。
题目分析
- 可通过先排序来解决这个问题，但是排序需要O(nlogn)的时间。可以考虑如下方法。
- n个数字都在0~n-1范围内。如果没有重复数字，则数组排好序后数字i将出现在数组i的下标下。如果有重复的数字，则某些位置将存在多个数字。
- 遍历整个数组ARR，当遍历到下标为i的数字m时：
- 如果i=m，则继续遍历下一个数字。
- 如果i!=m，则将m和ARR[m]比较，如果相等，则找到了重复数组，返回即可。如果不相等，则将第i个数字和第m个数字进行交换。
- 继续循环，直到发现相同的数字。
代码
int duplicate(int[] arr){
if (arr == null || arr.length <= 0) {
return -1;
}
for (int i = 0; i < arr.length; i++) {
while (arr[i] != i) {
if (arr[arr[i]] == arr[i]) {
return arr[i];
}
int tmp = arr[i];
arr[i] = arr[arr[i]];
arr[tmp] = tmp;
}
}
return -1;
}
