《剑指offer第二版》面试题3：数组中重复的数字（java）

题目描述

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中的某些数字是重复的，但不知道几个重复了，也不知道重复了几次。请找出数组中任意一个重复的数字。例如输入数组为{2,3,1,0,2,3,5}，那么对应的输出是重复的数字2或者3。

题目分析

1. 可通过先排序来解决这个问题，但是排序需要O(nlogn)的时间。可以考虑如下方法。
2. n个数字都在0~n-1范围内。如果没有重复数字，则数组排好序后数字i将出现在数组i的下标下。如果有重复的数字，则某些位置将存在多个数字。
3. 遍历整个数组ARR，当遍历到下标为i的数字m时：
   1. 如果i=m，则继续遍历下一个数字。
   2. 如果i!=m，则将m和ARR[m]比较，如果相等，则找到了重复数组，返回即可。如果不相等，则将第i个数字和第m个数字进行交换。
   3. 继续循环，直到发现相同的数字。

代码

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;
}