数组中重复的数字——剑指offer03

数组中重复的数字。

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

方法1

哈希表的结构是：key-value，key 就是数组中的数字，value=1 代表数字出现过。

整体的流程是：遍历数组中的数字，检查是否出现过，如果出现过，那么返回此数字。代码实现如下：

var findRepeatNumber = function(nums) { const map={}; for(var i=0;i<nums.length;i++){ if(map[nums[i]]==null){ map[nums[i]]=1; }else{ return nums[i]; } } };

方法2（原地hash）

由于数组中所有数字都在0 - n-1范围内，那么如果数组中没有重复的数字，那么数字 i 就一定出现在下标为 i 的位置。 所以在遍历数组的时候， 1.如果当前位置元素nums[i] 等于 i ，则继续遍历 2.否则，将nums[i]与nums[nums[i]]进行比较， 2.1 如果相等，则找到重复的元素 2.2 如果不等，将他们两个进行交换，把nums[i]放到对应的下标上去

var findRepeatNumber = function(nums) { for(var i=0;i<nums.length;i++){ while(i!=nums[i]&&nums[i]!=nums[nums[i]]){ var tmp=nums[i]; nums[i]=nums[nums[i]]; nums[tmp]=tmp; } if(i!=nums[i]&&nums[i]==nums[nums[i]]) return nums[i]; } };