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

通过率 67.8%

题目链接

题目描述：

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

思路：

首先想到的就是遍历数组，每遍历到一个元素，就用indexOf()方法从该位置后面开始查询，此元素是否再次出现

然后看题解了解到 map哈希表和原地置换法 ：

哈希表：遍历数组，当遍历到的元素不存在于map中，则添加到map中，否则就是重复元素
原地置换法：因为n个数字都在0~n-1范围内，可以利用这一特性优化：遍历数组，让元素值与其对应下标一致，一旦发现元素值与下标不等的，就将元素换到下标与该元素值相等的位置去，若目标位置的值本身就与该位置下标相等，说明出现重复数字

补充：

for..in..每次都是把索引/属性给变量；for..of..每次都是把索引对应的值/属性值给变量

方法has() 返回一个bool值，用来表明map 中是否存在指定元素.

1. indexOf()：

 1 /*JavaScript*/
 2 /**
 3  * @param {number[]} nums
 4  * @return {number}
 5  */
 6 var findRepeatNumber = function(nums) {
 7     for(let i=0; i<nums.length; i++) {
 8         if(nums.indexOf(nums[i], i+1)!=-1) {
 9             return nums[i];
10         }
11     }
12 };

2. 哈希表：

 1 /*JavaScript*/
 2 /**
 3  * @param {number[]} nums
 4  * @return {number}
 5  */
 6 var findRepeatNumber = function(nums) {
 7     //哈希表
 8     const map = new Map()
10     for(let i of nums) {
11         // if(map.get(nums[i]) !== undefined) //如果用get()判断，不要忽略了nums[i]===0的情况，须判断是否返回undefined
12         if(map.has(i)) // 方法has() 返回一个bool值，用来表明map 中是否存在指定元素.
13             return i
14         map.set(i, 0)
15     }
16 };

3. 原地置换法：

 1 /*JavaScript*/
 2 /**
 3  * @param {number[]} nums
 4  * @return {number}
 5  */
 6 var findRepeatNumber = function(nums) {
 7     //原地置换法
 8     for(let i=0; i<nums.length; i++) {
 9         while(nums[i] != i) {
10             var temp = nums[i];
11             if(nums[temp] == temp) {
12                 return temp;
13             }
14             nums[i] = nums[temp];
15             nums[temp] = temp;
16         }
17     }
18 };