「剑指 Offer 03. 数组中重复的数字」
- 创建
Set
- 遍历数组,判断当前元素是否在
Set
中出现过,若出现过,则直接返回该元素
- 若没出现过,将当前元素加入到
Set
const findRepeatNumber = nums => {
const set = new Set();
const len = nums.length;
for (let i = 0; i < len; i++) {
const num = nums[i];
if (set.has(num)) return num;
set.add(num);
}
};
- 从头遍历数组,若发现元素值和下标
i
不相等的,将该元素与下标i
对应的数交换,直到相等为止。
- 若发现元素值与下标i对应的数相等,则重复,返回元素值。
const findRepeatNumber = nums => {
let i = 0;
const len = nums.length;
while (i < len) {
// 若该数和下标相等,则i++,检查下一个数
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;
};