题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

思路1：逐个扫描，每个数都扫描一轮。时间复杂度是O(n^2)

public class Solution {
    // 返回任意重复的一个值，赋值duplication[0]，这是题目要求
    public boolean duplicate(int numbers[],int length,int [] duplication) {
       for (int i = 0; i < length; i++) {
          for (int j = i + 1; j < length; j++) {
             if (numbers[j] == numbers[i]) {
                 duplication[0] = numbers[i];
                 return true;
            }
        }
    }
    return false;
    }
}

思路2：利用排序，再从排序好的数组中找，排序好后只用扫一轮就可以，排序时间复杂度一般能优化到O(nlogn)

import java.util.Arrays;
public class Solution {

    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || length == 0){
            return false;
        }
        Arrays.sort(numbers);
        for(int i=0;i<length-1;i++){
            if(numbers[i] == numbers[i+1]){
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
}

思路3：利用哈希表或辅助数组，空间换时间，空间复杂度是O(n)，时间复杂度O(1)。当哈希表添加元素相同时，说明重复了（或者使用Hashmap记录次数，最后次数大于1的就是重复的）。自然，不用哈希表，可以用一个辅助数组来记录对应元素的角标，也是可以的(同样也可以用数组来记录次数)

import java.util.HashSet;
import java.util.Set;
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        Set<Integer> set = new HashSet<>();
        for(int i =0 ;i<length;i++){
            if(set.contains(numbers[i])){
                duplication[0] = numbers[i];
                return true;
            }else{
                set.add(numbers[i]);
            }
        }
        return false;
    }
}
//使用辅助数组的写法
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        int[] arr = new int[length];
        for(int j = 0;j<length;j++){
            arr[j] = -1;  //辅助数组赋初值，只要不在1到n-1即可，否则在后续判断时会出错
        }
        for(int i =0 ;i<length;i++){
            if(arr[numbers[i]] == numbers[i]){
                duplication[0] = numbers[i];
                return true;
            }else{
                arr[numbers[i]] = numbers[i];
            }
        }
        return false;
    }
}
//显然用来记录次数的辅助数组，不用赋初值  只要次数超过1就可以返回了，++的条件时次数为零
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        int[] arr = new int [length];
        for(int i = 0; i < length; i++){
            if(arr[numbers[i]] == 0){
                arr[numbers[i]] ++;
            }else{
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
}

思路4：这不是一个普通的具有重复数字的数组，利用条件--长度为n，数的范围1到n-1，因此如果每个数字都不重复时，排完序的数组中的元素值和该元素的索引相同，而一旦有重复的数，那就会出现，元素和角标不相同的情况，基于这个条件，构建思路4，也叫重排数组（其实和哈希表想法相似，当同一个位置元素出现多次时，说明重复了）这个想法需要不断交换对应的元素。
比如{4，1，3，1，4} ，将索引为0的4移动到索引为4的元素交换，让4归位，但是移动时发现索引为4的元素已经是4了，就说明出现了两次。

public class Solution {
        public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || length <= 0) {
            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;
    }
}

很显然，思路4打乱了原数组的顺序，但是空间复杂度较低

附：在剑指offer书中，本题还有一个附加题，那就是不允许打乱数组顺序，并且题目改为了长度为n+1，所有数字是1到n的范围。其余条件不变。显然之前的辅助数组的方法是可以的，如果辅助数组也不让用了。
书给出的解答方式是二分法：把1到n的数字从中间数字m分成两部分，若前一半1到m的数字数目超过m个，说明重复数字在前一半区间，否则，在后半区间m+1到n。每次在区间中都一分为二，直到找到重复数字。
整个时间复杂度是O(nlogn) 空间复杂度O(1).