备忘录

• 开辟新空间，值为n的存在下标为n+1的位置
• 要开辟额外空间

public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null) {
            return false;
        }
        int[] cache = new int[length];
        // 备忘录记录
        for(int num : numbers) {
            if(cache[num] == 0) {
                cache[num] = 1;
            } else {
                duplication[0] = num;
                return true;
            }
        }
        return false;
    }

交换法

• 从第一个开始，该值和下标不同就交换，相同就下一个，直到走完
• 不能保证找出第一个最小值

 public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null) {
            return false;
        }
        int i = 0;
        while(i < length) {
            if(numbers[numbers[i]] != numbers[i]) {
               int temp = numbers[numbers[i]];
               numbers[numbers[i]] = numbers[i];
               numbers[i] = temp;
            } else if(i == numbers[i]){
                i++;
            } else {
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }