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, 0for {fast = nums[nums[fast]]slow = nums[slow]if fast == slow {fast = 0for fast != slow {fast = nums[fast]slow = nums[slow]}return slow}}return 0
}

func findDuplicate(nums []int) int {n := len(nums)ans := 0for 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
}