题目 03. 数组中重复的数字

方法一：哈希遍历一次过！

思路： 申请一个hashset，然后遍历数组，对数组中的每一个元素作如下操作：

检查hashset中是否包含该元素； 如果包含，说明该元素是重复的，直接返回；若不包含，则将该元素添加到集合中；

代码

class Solution { public int findRepeatNumber(int[] nums) { HashSet<Integer> hashset = new HashSet<>(); for(int i = 0; i < nums.length; i ++){ if(hashset.contains(nums[i])){ return nums[i]; }else{ hashset.add(nums[i]); } } return -1; } }

方法二：不需要额外空间

之前在360面试中遇到过这道题，一上来就按照上面的方法咔咔地敲出来了，面试官微微一笑，不错，可不可以不借助hashset，当时一脸茫然不知所措了。。

分析：

将所给的数组顺序排列的话，如果没有重复的数字，那么元素与其索引将会是相同的。因此，我们按照正序的原则，只需在遍历每个元素的时候看看，如果元素不是在其索引上，则将它放置它应该在的位置。

而在交换位置的同时，我们发现它和它应该在的位置上的元素相同，则返回该元素。（出现这情况有两种情况，一是恰好在它应该在的位置上遇到了重复的，二是已经遍历过该元素，它位置上的元素就是上次遍历后处理的结果）

思路

先查看该元素e是不是在应该在的位置nums[e]，是的话就跳过，不是就下一步；把该元素放在它应该在的位置上； 如果它应该在的位置上已经有正确的元素了，那么就返回，说明重复了。

代码

class Solution { public int findRepeatNumber(int[] nums) { int len = nums.length; int tmp; for(int i = 0; i < len; i++){ int e = nums[i]; if(e != i){ //将它放在应该在的位置 if(e == nums[e]){ return e; }else{ tmp = e; e = nums[tmp]; nums[tmp] = tmp; } } } return -1; } }