剑指Offer（五十）-- 数组中重复的数字
Github仓库地址：https://github.com/Damaer/CodeSolution 刷题笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是第一个重复的数字2。没有重复的数字返回-1。
示例1
输入
[2,3,1,0,2,5,3]
返回值
2
思路以及解答
我们首先可能想到的做法，就是借助set，如果元素不存在set中，就将元素添加进去，如果set中包含该元素，就返回该元素即可。如果一直都没有重复的，那么最后返回-1。
代码如下：
import java.util.*;
public class Solution {
public int duplicate(int[] numbers) {
// write code here
if(numbers!=null) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < numbers.length; i++) {
if (set.contains(numbers[i])) {
return numbers[i];
} else {
set.add(numbers[i]);
}
}
}
return -1;
}
}
时间复杂度为O(n)，因为最差的情况可能遍历完所有的元素；空间复杂度也是O(n)，最大需要set大小为n。
当然除了set，我们也可以直接借助数组，因为所有数字都在0到n-1的范围内，我们用一个大小为n的数组，就可以对所有的数字进行统计个数，如果个数超过1，那么肯定是重复的数字，如果没有重复的数字，则返回-1；
public class Solution {
public int duplicate(int[] numbers) {
if(numbers!=null) {
int[] nums = new int[numbers.length];
for (int i = 0; i < numbers.length; i++) {
if (nums[numbers[i]]==1) {
return numbers[i];
} else {
nums[numbers[i]]=1;
}
}
}
return -1;
}
}
同样这种做法的时间复杂度和空间复杂度都是O(n)。
那么有没有空间复杂度为O(1)的做法呢？肯定是有的，不借助额外的空间，那么就只能操作原数组了。如果没有重复的情况，那么这些数字排序后，数字i和数组下标i应该是一一对应的。不会出现多个数字i的情况。
基于这个原则，我们在遍历数组的时候，将元素i调整到下标i的位置，如果下标i的位置已经有元素，那么说明冲突了，这个元素肯定是重复的，否则继续调整后面的。如果没有发现重复的数字，就返回-1。
public class Solution {
public int duplicate(int[] numbers) {
int i = 0;
while(i < numbers.length) {
if(numbers[i] == i) {
i++;
continue;
}
if(numbers[numbers[i]] == numbers[i]) return numbers[i];
int tmp = numbers[i];
numbers[i] = numbers[tmp];
numbers[tmp] = tmp;
}
return -1;
}
}
但是上面的做法，不适合求解多个重复数字的例子，因为调换的时候，很容易将后面的数字换到前面去，就会导致求解出来不是第一个重复的数字（可以用来求解任意的重复数字），可能是第2，3...或者其他的重复数字。譬如：[6,3,2,0,2,5,0]正确的解应该是 2 ，但是由于第一次把6和最后的0调换了位置，就会导致求解出来的值为 0 。
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。
平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -
腾讯云开发者
