LeetCode 287 寻找重复数

1.自己的做法

class Solution { public int findDuplicate(int[] nums) { int i; for(i=0;i<nums.length;i++){ while(nums[i]!=i+1&&nums[i]!=nums[nums[i]-1]){ int temp=nums[i]; nums[i]=nums[temp-1]; nums[temp-1]=temp; } if(nums[i]!=i+1&&nums[i]==nums[nums[i]-1]) return nums[i]; } return nums[i]; } }

class Solution { public int findDuplicate(int[] nums) { int i; for(i=0;i<nums.length;i++){ while(nums[i]!=i+1){ if(nums[i]==nums[nums[i]-1]) return nums[i]; int temp=nums[i]; nums[i]=nums[temp-1]; nums[temp-1]=temp; } } return nums[i]; } }

在while循环的过程中，会把每一个该放在哪的数字放在它该放的位置上，

如果发现这个位置已经有了和它相等的数字证明就是它重复 

2.借助hashset不重复元素

class Solution { public int findDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(); for(int i=0;i<nums.length;i++){ if(!set.add(nums[i])) return nums[i]; } return 0; } }

 

3.快慢指针

class Solution { public int findDuplicate(int[] nums) { int slow=0,fast=0; do{ slow=nums[slow]; fast=nums[nums[fast]]; }while(slow!=fast); slow=0; while(slow!=fast){ slow=nums[slow]; fast=nums[fast]; } return slow; } }

 

这个快慢指针我曾经花了好长时间也没有想明白，能看懂别人解释的证明，但就是没法理解