287.寻找重复数

题解

题目：给一个数组，元素大小1~n,其中有一个数出现两次，要求用O(1)的空间复杂度求出这个出现两次的元素，并且不能修改原数组

思路：

快慢指针

取巧

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
}