找到数组中重复的数字
题目描述
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例：
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
解法一： 哈希表
从题目中分析，只需要找到任意一个重复的数字，那么可以利用哈希表，用数字的值作为 key 去存储，如果遇到已经存在的 key，则直接返回，这样就找到了重复的数字。
算法步骤
- 声明哈希表用来保存遍历的值。
- 开始遍历数组。
- 获取当前值，判断值是否已经存在，若存在，则返回结果并结束循环；若不存在，则继续下一步。
- 储存当前值进哈希表。
- 处理数组下一位，重复直到遍历完成。
/**
* @param {number[]} nums
* @return {number}
*/
const findRepeatNumber = function (nums) {
// 定义 hash 表
let map = new Map();
let i = 0;
while (i < nums.length) {
// 如果存在当前数字，那么直接结束循环，返回当前数字
if (map.has(nums[i])) {
return map.get(nums[i]);
}
// 储存已经遍历过的值
map.set(nums[i], nums[i]);
i++;
}
};
复杂度分析
- 时间复杂度 O(N)：遍历一遍数组既可完成。
- 空间复杂度 O(N)：需要声明哈希表进行存储。
解法二： 原地交换
我们可以把数组的值，交换到与该值相等的索引的位置。如果交换时发现，该索引的位置已经存在与当前值相等的值，则结束操作并返回当前值。
算法步骤
- 遍历数组。
- 判断当前值和索引是否相等，如果是，直接跳过处理下一个元素，不是，则进行下一步。
- 判断需要交换的索引位置的值，是否和当前值相等，如果是，则返回当前值并结束，不是，则进行下一步。
- 将当前值和对应索引位置的元素进行交换。
- 依次处理完全部元素。
/**
* @param {number[]} nums
* @return {number}
*/
const findRepeatNumber = function (nums) {
let i = 0;
while (i < nums.length) {
// 如果当前值等于索引，那么直接跳过
if (nums[i] === i) {
i++;
continue;
}
// 如果需要交换的索引位置已经存在相同值，直接结束，返回当前值
if (nums[nums[i]] === nums[i]) {
return nums[i];
}
// 交换当前值，和对应索引存在的值
[nums[nums[i]], nums[i]] = [nums[i], nums[nums[i]]];
}
return -1;
};
复杂度分析
- 时间复杂度 O(N)：每个元素最多被移动 2 次。
- 空间复杂度 O(1)：不需要额外的空间完成。