剑指 Offer 3. 数组中重复的数字

🟢   🔖  数组 哈希表 排序  🔗 LeetCode

题目

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

例如，如果输入长度为 7 的数组[2,3,1,0,2,5,3]，那么对应的输出是 2 或者 3。存在不合法的输入的话输出-1.

Example:

输入：[2, 5, 3, 0, 5, 0]

输出：0 或 5

Constraints:

• 数据范围：0 ≤ n ≤ 10000
• 进阶：时间复杂度 O(n) ，空间复杂度 O(n)

解题思路

使用哈希表，遍历数组，如果 map 中不存在该元素则保存它，如果 map 中已经存在该元素，立即返回。

代码

/**
 * @param {number[]} documents
 * @return {number}
 */
var findRepeatDocument = function (documents) {
	let map = new Map();
	for (let i of documents) {
		if (map.has(i)) return i;
		map.set(i, true);
	}
	return -1;
};