数组中重复的数字
问题描述：
找出数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字
解题思路
字典法
- 使用
HashSet或者 数组来记录已遍历的数字，如果找到重复的数字，则返回 - 时间复杂度：
O(n)，空间复杂度：O(n)，需要额外空间
class Solution {
public int findRepeatNumber(int[] nums) {
// hashSet
if (nums == null || nums.length == 0)
return -1;
int n = nums.length, ans = -1;
int[] count = new int[n];
for (int num: nums) {
if (count[num] != 0) {
ans = num;
break;
}
count[num]++;
}
return ans;
// int[]
if (nums == null || nums.length == 0)
return -1;
int ans = -1;
Set<Integer> set = new HashSet<>();
for (int num: nums) {
if (!set.add(num)) {
ans = num;
break;
}
set.add(num);
}
return ans;
}
}
排序法
- 先排序，然后遍历数组，如果相邻元素相等，则返回
- 时间复杂度：
O(nlogn)，空间复杂度：O(1)，不需要额外空间，修改输入数组
class Solution {
public int findRepeatNumber(int[] nums) {
// 排序
if (nums == null || nums.length == 0)
return -1;
int n = nums.length, ans = -1;
Arrays.sort(nums);
for (int i = 0; i < n - 1; ++i) {
if (nums[i] == nums[i + 1]) {
ans = nums[i];
break;
}
}
return ans;
}
}
置换法
- 置换法，值为
x的元素，置换到数组索引为x的位置。如果当前元素值等于索引值，则继续进行遍历，如果不相等，则将nums[x]置换到正确的位置上，即nums[nums[x]]，如果在这个过程中，数组nums[x]索引下的值已经为nums[nums[x]]，则说明nums[x]重复，返回即可 - 时间复杂度：
O(n)，空间复杂度：O(1)，不需要额外空间，修改输入数组。虽然for循环里面套了while，但是每一个数来到它应该在的位置以后，位置就不会再变化。这里用到的是均摊复杂度分析的方法：如果在某一个位置while循环体执行的次数较多，那么一定在后面的几个位置，根本不会执行while循环体内的代码，也就是说最坏的情况不会一直出现。也就是说最坏复杂度的情况不会一直出现。
class Solution {
public int findRepeatNumber(int[] nums) {
// 交换
if (nums == null || nums.length == 0)
return -1;
int n = nums.length, ans = -1;
for (int i = 0; i < n; ++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 ans;
}
}
拓展
与上面题类似，但因为数组长度和数组元素限制的特点，解题思路不同
- 二分法
- 快慢指针法
