一、问题
找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。限制：2 <= n <= 100000
示例：输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3
二、解答
1️⃣HashSet
由于只需要找出数组中任意一个重复的数字，因此遍历数组，遇到重复的数字即返回。为了判断一个数字是否重复遇到，使用集合存储已经遇到的数字，如果遇到的一个数字已经在集合中，则当前的数字是重复数字。
初始化集合为空集合，重复的数字 repeat = -1
遍历数组中的每个元素：
将该元素加入集合中，判断是否添加成功
如果添加失败，说明该元素已经在集合中，因此该元素是重复元素，将该元素的值赋给 repeat，并结束遍历。返回 repeat。
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
int repeat = -1;
for (int num : nums) {
if (!set.add(num)) {
repeat = num;
break;
}
}
return repeat;
}
①时间复杂度：O(n)。
遍历数组一遍。使用哈希集合 HashSet，添加元素的时间复杂度为 O(1)，故总的时间复杂度是 O(n)。
②空间复杂度：O(n)。不重复的每个元素都可能存入集合，因此占用 O(n) 额外空间。
public static int findRepeatNumber(int[] nums) {
// HashSet
HashSet<Integer> set = new HashSet<Integer>();
for (int x : nums) {
//发现某元素存在，返回
if (set.contains(x)) {
return x;
}
//存入哈希表
set.add(x);
}
return -1;
}
2️⃣原地置换
大体思路就是将指针对应的元素放到属于它的位置(索引对应的地方)。可以这样理解，每个人都有自己的位置，需要和别人调换回到属于自己的位置，调换之后，如果发现自己的位置上有人了，则返回。一个萝卜一个坑，由于长度为 n 的数组内所有数字都在 1~n-1，那么元素与下标之间就可以存在一一对应的关系，即将“正确”的元素放到“正确”的位置，把 0 放到 nums[0]，把 1 放到 nums[1]...如果“正确”的位置上已经存在了“正确”的元素，说明该位置的元素就是重复的元素，返回即可。如果“正确”的位置上没有存放“正确”的元素，就进行交换，将“正确”的元素放到正确的位置。
public static int findRepeatNumber(int[] nums) {
if (nums.length == 0) {
return -1;
}
for (int i = 0; i < nums.length; ++i) {
while (nums[i] != i) {
// 如果对应位置已经存在该元素，说明重复
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
//置换，将指针下的元素换到属于它的索引处
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return -1;
}
①时间复杂度：O(n)。
②空间复杂度：O(1)。
3️⃣排序
由于长度为 n 的数组内所有数字都在 1~n-1 之间，所以排序后，重复数字必然相邻，由于只需要找出任意一个重复元素即可，返回第一个相邻元素即可。
public static int findRepeatNumber(int[] nums) {
// 排序后的数组，重复元素必然相邻
Arrays.sort(nums);
// 结果集
int res = 0;
for (int i = 0; i < nums.length - 1; i++) {
// 找到重复元素
if (nums[i] == nums[i + 1]) {
res = nums[i];
break;
}
}
return res;
}
①时间复杂度：排序是最容易想到的方式，但是由于多了一个排序过程，即使是快排，其时间复杂度也是 O(logn)，排序后还要遍历有序数组，时间复杂度 O(n)，总时间复杂度为 O(nlogn)。
②空间复杂度：O(1)。
