剑指offer 3. 数组中重复的数字

1. 空间复杂度O(n),时间复杂度O(n) 思路：通过定义长度N的数组，空间复杂度高一点，但易理解

public class Solution {

    public boolean duplicate(int numbers[],int length,int [] duplication) {
        // 1. 长度为0，不重复
        if(length == 0){
            return false;
        }
        // 2. 创建长度为N的数组往里设置值（规则下标与值相同，当第二次设置时便为重复值）
        Integer[] temp = new Integer[length];    
        for(int i = 0; i< length; i++){
           if(temp[numbers[i]] == null) {
              temp[numbers[i]] = numbers[i];
               continue;
           }
          duplication[0] = numbers[i];
          return true;
        }
        // 3. 设置完成未找到重复值，不重复
        return false;
    }
}

2. 空间复杂度O(1),时间复杂度O(n)

思路：原数组交换，易出问题 badCase： [6,3,2,0,2,5,0] 输出：true 0 但是2是第一个重复的数字，此方式优先将0输出

public class Solution {
  
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(length == 0){
            return false;
        }
        for(int i = 0; i< length; i++){
            int temp = 0;
            while(numbers[i] != i){
                // 将numbers[i]放入相应的位置，
                // 若当前位置已经存在该元素则重复
                if(numbers[numbers[i]] == numbers[i]){
                    duplication[0] = numbers[i];
                    return true;
                }
                // 若当前位置不存在元素则放入
                temp = numbers[numbers[i]];
                numbers[numbers[i]] = numbers[i];
                numbers[i] = temp;
            }
        }
        return false;
    }
}