数组中重复的数（时间复杂度，空间复杂度最优）

数组相关的算法（均为剑指offer思路，我只是在看书学习的时候做一个记录）
题目描述：
在一个长度为n的数组中所有的数字都在0~n-1的范围内，数组中的某些数字是重复的，但不知道有几个数字是重复的，现在需要些一个算法来求出重复的数字。
这道题的思路有1：使用一个hash表，在时间复杂度为n的情况下就可以求出来，但是空间复杂度是比较大的。
2：重排数组，因为题中的条件是数字的范围是在0——n-1中，所以，值需要从头比对当前位置上面的数值是否和本来应该出现的位置上面的数字一样就行了 。

代码：

public static void main(String args[]) {
    
    int arr[] = {2,3,1,0,2,5,3};
    int a = slove(arr);
    System.out.println(a);
    
}
public static int slove(int arr[]) {
    int len = arr.length;
    if (len == 0) {
        return -1;
    }
    for (int i = 0; i< len; i++) {
        if (arr[i]<0 || arr[i]> len-1) {
            return -1;
        }
    }
    for (int i = 0; i< len; i++) {
        while(arr[i] != i) {
            if (arr[i] == arr[arr[i]]) {
                return arr[i];
            }
            int temp = arr[i];
            arr[i]  =arr[temp];
            arr[temp] = temp;
        }
    }
    return -1;
}

题目描述：
在一个长度为n+1的数组中所有的数字都在1——n的范围内，数组中的某些数字是重复的，但不知道有几个数字是重复的，现在需要些一个算法来求出重复的数字。
利用二分的思路来解决这道问题，以时间复杂度来换取空间复杂度，将数字平均划分，最终落到一个范围内，如果在这个范围内，数组中的数字和大于现在的范围，那么可以得出的结论就是重复的数字就在这个二分后的范围内，所以将范围划分到为1之后就可以得到要求的重复数字了。
代码：

 public static void main(String args[]) {
    
    int arr[] = {2,3,5,4,3,2,6,7};
    int a = slove(arr);
    System.out.println(a);
    
}
public static int slove(int arr[]) {
    
    int len = arr.length;
    if (len <= 0) {
        return -1;
    }
    int start = 1;
    int end = len-1;

    
    while(start <= end) {
        int mid = (end+start)/2;
        int sum = count(arr,len,start,mid);
        if (start == end) {
            if (sum > 1) {
                return start; 
            }else {
                break;
            }
        }
        if (sum > (mid- start)+1) {
            end = mid;
        }else {
            start = mid+1;
        }
    }
    return -1;
}
public static int count(int arr[], int len,int start, int end) {
    
    int sum = 0;
    for (int i = 0; i< len; i++) {
        if (arr[i]>=start && arr[i]<= end) {
            sum++;
        }
    }
    return sum;
}