数组中重复的数字（剑指Offer 03）

题目

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例

输入：[2, 3, 1, 0, 2, 5, 3] 输出：2 或 3

限制

• 2 <= n <= 100000

算法

set

export const findRepeatNumber = (nums) => {
	const set = new Set();
	for (let i = 0; i < nums.length; i++) {
		if (set.has(nums[i])) {
			return nums[i];
		} else {
			set.add(nums[i]);
		}
	}
	return -1;
};

原地置换

因为题目中说数组长度为n且元素范围是[0, n-1]，所以如果数组中没有重复元素，则每一个数字nums[i]都应该在下标为i的位置，反之如果有重复，则必定存在在位置i上有两个重复的数字nums[i]

遍历数组，如果位置i上的数字是nums[i]则继续遍历，否则交换nums[i]和nums[nums[i]]，直到该位置数字是i，如果存在nums[i]和nums[nums[i]]上数字重复，则说明这就是重复数字，直接返回数字nums[i]

export const findRepeatNumber = (nums) => {
	let temp;
	for (let i = 0; i < nums.length; i++) {
		while (nums[i] !== i) {
			if (nums[i] === nums[nums[i]]) return nums[i];
			temp = nums[i];
			nums[i] = nums[temp];
			nums[temp] = temp;
		}
	}
	return -1;
};