数组中重复的数字

描述

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

数据范围：0≤ n ≤10000

进阶：

• 时间复杂度O(n)
• 空间复杂度O(n)

示例1

输入： [2,3,1,0,2,5,3]

返回值：2

说明：2或3都是对的

解法一：利用set集合

• 引入set集合，遍历数组元素，检查元素是否在集合中，不在则将元素插入到集合里面；
• 否则表明当前元素在数组中重复，返回当前元素。

public static int duplicate(int[] numbers) {
        // 1、定义一个set
        HashSet<Integer> hashset = new HashSet<>();
        // 2、遍历数组
        for (int i : numbers) {
            // 3、判断集合中是否存在当然i
            if (hashset.contains(i)) {
                // 4、存在，返回i，即偶重复的
                return i;
            } else {
                // 5、没有重复的，添加到set集合中
                hashset.add(i);
            }
        }
        return -1;
    }

复杂度分析：

• 时间复杂度O(N)：代码使用了循环，循环次数为数组大小
• 空间复杂度O(N)：引入额外的集合空间

解法二：新建数组

• 新建一个数组，将原数组中的每一个数字当做新数组的下标，而新数组中存放每个下标出现的次数
• 把numbers[i] 作为 res[]的下标，即res[ numbers [ i ] ]
• res[ ]++，记录出现的次数

if (numbers == null || numbers.length == 0) {
            return -1;
        }
        // 1、定义一个新数组
        int[] res = new int[numbers.length];
        // 2、遍历numbers
        for (int i : numbers) {
            // 3、把numbers[i] 作为 res[]的下标，即res[numbers[i]]
            res[i]++;
            // 判断是否重复
            if (res[i] == 2) {
              // 重复了，返回当前数字
                return i;
            }
        }
        return -1;