题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

解题思路

使用集合遍历 时间复杂度O(n) 空间复杂度O(n)

这个是最容易想到的方法，集合中Set可以完美的得出结论

    public int duplicate(int[] numbers) {
        Set<Integer> set = new HashSet<>();
        // 遍历numbers
        for (int number : numbers) {
        // 如果集合中已经存在
            if (set.contains(number)) {
                // 返回结果
                return number;
            }
            // 如果不存在就添加
            set.add(number);
        }    
        // 如果没有找到重复的
        return -1;
    }

使用数组本身遍历 时间复杂度O(n) 空间复杂度O(1)

如果使用数组本身作为存储的容器，那么所需要的额外内存将会是O(1)，因为数组中存储的值是0~n-1，那么我们可以每个数都与其下标相等，如果当前下标已经存在与它相等的数，那么此数就为重复的数

1.  public static int duplicate(int[] numbers) {
        // 外层循环从下标为0开始
        for (int i = 0; i < numbers.length; i++) {
            // 如果当前值不等于其下标
            while (numbers[i] != i){
                // 如果当前值是否已经有重复
                if (numbers[i] == numbers[numbers[i]]) {
                    return numbers[i];
                }
                // 不满足条件就交换
                int temp = numbers[numbers[i]];
                numbers[numbers[i]] = numbers[i];
                numbers[i] = temp;
            }
        }
        return -1;
    }

2. 举个例子
   1. 假设数组为[2,3,1,0,2,5,3]
      i = 0 :

       第一次交换后数组为[1, 3, 2, 0, 2, 5, 3]
       第二次交换后数组为[3, 1, 2, 0, 2, 5, 3]
       第三次交换后数组为[0, 1, 2, 3, 2, 5, 3]
       跳出while循环

      i = 1

       满足numbers[i]等于i)

      i = 2

        满足numbers[i]等于i)

      i = 3

        满足numbers[i]等于i)

      i = 4

       进入while循环， 满足numbers[i]等于 numbers[numbers[i]]输出2