题解 | #数组中重复的数字#
数组中重复的数字
http://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524
数组中重复的数字
描述
在一个长度为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;
查看12道真题和解析
