287.M 寻找重复数

Problem: 287. 寻找重复数

思路

思路1：二分法 使用count统计值小于等于mid的元素的个数

• 如果个数大于mid，说明重复的数字在左侧，而且有可能是mid，因此设置right为mid

• 否则，说明应该查找右侧，而且不包括mid，因此设置left为mid+1

思路2：快慢指针 把数字想象为一个链表，每个元素的值表示下一步应该访问的元素的位置，找重复数就相当于找链表环的入口

Code

代码1：

func findDuplicate(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		count := 0
		for _, num := range nums {
			if num <= mid {
				count++
			}
		}

		if count > mid {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

代码2：

func findDuplicate(nums []int) int {
	slow := nums[0]
	fast := nums[nums[0]]
	//找到相遇点
	for slow != fast {
		slow = nums[slow]
		fast = nums[nums[fast]]
	}

	//找到环的入口
	fast = 0
	for slow != fast {
		slow = nums[slow]
		fast = nums[fast]
	}

	return slow
}