287.寻找重复数
287.寻找重复数
题解
题目：给一个数组，元素大小1~n,其中有一个数出现两次，要求用O(1)的空间复杂度求出这个出现两次的元素，并且不能修改原数组
思路：
快慢指针
1.快慢指针起始位置可以在0,0 也可以在0,1,总之fast总会和slow相遇，但是我比较喜欢写在0，0，不必纠结 2.可以将数组看作一个链表，比如[2,3,1,2],下标是[0,1,2,3] 3.则[0>2,1>3,2>1,3>2]---->2,1,3,2,1,3,2,1,3... 4.可以发现，这个链表是成环的，那么此题就变成了这一题 golang力扣leetcode 142.环形链表II https://blog.csdn.net/qq_42956653/article/details/121689370 5.此题的入环点就是重复的数字，任何求入环点呢？ 6.牢记：从相遇点到入环点的距离，恰好等于从链表头部到入环点的距离。
取巧
1.取出一个数，将其对应的下标上的数变号 2.如果遇到已经变号的数，说明之前被变号了，既然是1~n,说明现在遍历的这个数肯定是重复的 3.将原数组都回正 4.其实这种方法，感觉不满足“不能修改原数组”这个要求，擦边了，还是用第一种吧
代码
func findDuplicate(nums []int) int { fast, slow := 0, 0 for { fast = nums[nums[fast]] slow = nums[slow] if fast == slow { fast = 0 for fast != slow { fast = nums[fast] slow = nums[slow] } return slow } } return 0 }
func findDuplicate(nums []int) int { n := len(nums) ans := 0 for i := 0; i < n; i++ { v := abs(nums[i]) if nums[v-1] > 0 { nums[v-1] *= -1 } else { ans = v } } for i := 0; i < n; i++ { if nums[i] < 0 { nums[i] *= -1 } } return ans } func abs(i int) int { if i < 0 { return -i } return i }
