- 👑专栏内容：力扣刷题
- ⛪个人主页：子夜的星的主页
- 💕座右铭：前路未远，步履不停
一、题目描述
1、题目
剑指offer：数组中重复的数字
在一个长度为 n 的数组里的所有数字都在 0 0 0 到 n − 1 n-1 n−1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组 [ 2 , 3 , 1 , 0 , 2 , 5 , 3 ] [2,3,1,0,2,5,3] [2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1。
数据范围：
0
≤
n
≤
10000
0≤n≤10000
0≤n≤10000
进阶：时间复杂度
O
(
n
)
O(n)
O(n) ，空间复杂度
O
(
n
)
O(n)
O(n)
2、示例
输入：[2,3,1,0,2,5,3]
返回值：2
说明：2或3都是对的
二、题目分析
题目的意思非常简单，一句话总结就是：一个特定范围内的数组中找到任意一个重复的数字。
1、双重for循环
public class Solution {
public static int duplicate(int[] numbers) {
for(int i =0;i<numbers.length;i++){
for (int j = i+1; j <numbers.length ; j++) {
if(numbers[i] == numbers[j])
return numbers[i];
}
}
return -1;
}
}
通过循环来比较数组中的每一对元素来查找重复。
时间复杂度是
O
(
n
2
)
O(n^2)
O(n2)：因为有两个嵌套循环，每个循环都遍历整个数组。
空间复杂度是
O
(
1
)
O(1)
O(1)：没有使用除了输入数组之外的额外空间。
2、for-each 循环
public class Solution {
public static int duplicate(int[] numbers) {
int [] res = new int[numbers.length];
for(int i:numbers){
res[i]++;
if(res[i] > 1){
return i;
}
}
return -1;
}
}
使用一个额外的数组来记录每个数字出现的次数。一旦某个数字的出现次数超过1，就立即返回该数字。在时间上更高效，但牺牲了一些空间来达到这个目的。
时间复杂度：
O
(
n
)
O(n)
O(n)。只有一个循环，遍历一次数组。
空间复杂度：
O
(
n
)
O(n)
O(n)。使用了一个与输入数组同等大小的额外数组来记录每个数字出现的次数。
3、set集合
public class Solution {
public static int duplicate(int[] numbers) {
Set<Integer> set = new HashSet<Integer>();
for(int i : numbers){
if(set.contains(i)){
return i;
}else{
set.add(i);
}
}
return -1;
}
}
创建一个 HashSet，在循环内部，首先检查当前元素 i 是否已经在 set 中：文章来源：https://www.toymoban.com/news/detail-807075.html
- 如果
set已包含i，则返回i作为第一个重复的元素。 - 如果
set不包含i，则将i添加到set中，然后继续循环。
时间复杂度是
O
(
n
)
O(n)
O(n)，空间复杂度是
O
(
n
)
O(n)
O(n)：使用了一个额外的 HashSet 来存储元素。在最坏情况下（没有重复元素），这个集合将包含所有 n 个元素。文章来源地址https://www.toymoban.com/news/detail-807075.html
到了这里，关于【剑指offer】数组中重复的数字的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
