Find the Duplicate Number
你会得到一个包含 n+1 个整数的数组 nums，每个整数都在 1 到 n 之间。恰好有一个值出现了多次，出现次数可能很多，你要返回这个值。
在不修改 nums 且只使用常量额外内存的情况下解决这个问题。
函数
- numsinteger-array
- n+1 个整数，每个都在 1 到 n 之间
- 返回值integer
- 出现多次的值
约束条件
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- 恰好有一个值出现两次或更多次；其他每个值最多出现一次。
示例
- 输入
- nums = [2, 5, 1, 3, 5, 4]
- 输出
- 5
- 解释
- 这里
n是 5，5 位于位置 1 和 4，因此答案是 5。1 到 5 中的其他每个值都只出现一次。
- 输入
- nums = [4, 2, 4, 1, 4]
- 输出
- 4
- 解释
- 4 出现了 3 次，位置分别是 0、2 和 4，而 3 一次也没有出现。一个重复值可以代替多个缺失值，所以答案是 4。
进阶
按值进行二分查找会使两条规则都保持在 O(n log n) 时间内。你能让它们保持在 O(n) 时间内吗？
提示
逐个打开提示，每个都会多透露一点。
每个值都在 1 到
n之间，数组的位置是 0 到n。因此，每个值也都是有效的位置。从位置 0 开始，跳到位置nums[0]，然后跳到该位置上的值所指向的位置，以此类推。这段行走一定会发生什么？这个遍历永不停止，而且只有
n+1个位置需要访问，因此会陷入循环。它进入循环的位置可以从两个不同的位置到达，而这两个位置都以该位置作为自己的值。让两个指针都从位置 0 出发，寻找循环入口：一个指针每轮跳一步，另一个跳两步，直到它们落在同一位置。然后把其中一个指针移回位置 0，再让两个指针每次都跳一步。它们相遇的位置就是入口，也就是答案。
题解
哈希集合需要为每个值分配内存，而排序会改变 nums。每个值都介于 1 和 n 之间，因此它也可以作为有效位置：把它看作一条链接。从位置 0 开始遍历，最终会进入一个循环，循环入口就是重复值。Floyd 的双指针可以在 O(n) 时间内找到它。
比较每一对
结果正确，但无法在最大的测试中运行完毕
思路
将每个位置与它后面的每个位置进行比较，并返回第一对相等位置的值。不会写入任何内容，且只使用两个计数器，因此这两条规则都满足。对于 10,001 个值，如果两个副本都接近末尾，就需要进行约 5 × 10^7 次成对检查。
算法
- 对于从 0 到末尾的每个位置
i： - 对于
i之后的每个位置j，比较nums[i]和nums[j]。 - 在首次匹配时返回
nums[i]。
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeat按值进行二分搜索
思路
搜索值的范围，而不是位置。对于截止值 m，统计小于或等于 m 的元素数量。如果重复值 d 大于 m，那么从 1 到 m 的每个值都至多出现一次，因此数量至多为 m。如果 d 小于或等于 m，那么大于 m 的元素至多有 n-m 个，因此小于或等于 m 的元素至少有 m+1 个。测试条件 "count > m" 在 d 以下为假，从 d 开始为真，二分查找就能找到它首次变为真的 m。
在第二个示例中，m = 2 时，统计到 2 和 1，不超过 2；m = 3 时，统计结果仍为 2，所以答案是 4。每轮都会读取一次数组：大约需要扫描 10,001 个值 14 次。
算法
- 将
low设为 1，将high设为n，也就是nums的长度减一。 - 当
low < high时，取它们中间的mid。 - 统计
nums中小于或等于mid的元素个数。 - 如果个数大于
mid，将high设为mid；否则将low设为mid+1。 - 返回
low。
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return low对值链接使用 Floyd 环检测
思路
把数组看作一组链接：位置 i 指向位置 nums[i]。有 n+1 个位置，且每个位置都有一个链接，从 0 出发遍历时必定会再次到达某个位置：先经过一段尾部，然后进入一个循环。第一个示例的遍历顺序是 0、2、1，然后绕过 5、4。
循环入口有两个位置指向它，一个在尾部，一个在循环中：这里是位置 1 和 4，它们的值都是 5。没有任何值是 0，所以位置 0 总是在尾部上，循环入口总有两条路径指向它。只有一个值重复，因此循环入口就是答案。
第一阶段中，slow 每轮沿一个链接移动，fast 每轮沿两个链接移动，直到它们在第 s 轮后相遇。fast 多走的 s 步正好是若干整圈。第二阶段将 slow 重新放回 0。走过 T 步后，尾部长度为 T，slow 位于循环入口，而 fast 位于从 0 出发走 T 步再加上若干整圈后的位置：也在循环入口。
算法
- 将每个位置
i视为一个指向位置nums[i]的节点，并将两个指针都从位置 0 开始。 - 阶段 1：让
slow移动到nums[slow]，让fast移动到nums[nums[fast]]，直到它们相等。 - 阶段 2：将
slow重新设为 0。 - 每次移动一个链接，让
slow移动到nums[slow]，让fast移动到nums[fast]，直到它们相等。 - 返回该位置：它就是重复的值。
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
易错点和边界情况
- 返回第 1 阶段的相遇点。它位于循环中的某处：在第一个示例中，指针在 4 处相遇，但答案是 5。
- 在第一次移动前检查
slow == fast。两者都从 0 开始，所以循环会立即结束。 - 从位置 0 以外的位置开始移动。在第一个示例中，位置 3 指向自身，这是一个没有入口的循环，因此它的入口无法证明任何事情。
- 在二分查找中测试
count >= mid。当从 1 到m的值没有重复或缺失时，计数恰好是m，因此只有>才能区分两侧。 - 通过将条目取负或把值交换到对应位置来标记已访问的值。这两种方法都能找到答案，但都会修改数组。
常见问题3
“Find the Duplicate Number”的时间复杂度是多少？
Floyd 环检测的时间复杂度为 O(n)，额外空间复杂度为 O(1)。对值进行二分查找的时间复杂度为 O(n log n)，空间复杂度为 O(1)；比较每一对元素的时间复杂度为 O(n²)。
为什么不使用哈希集合或对数组排序？
在真实程序中，两种方法都可行。题目不允许使用这两种方法：哈希集合会占用 O(n) 的额外内存，而排序会改变 nums，或者需要完整复制一份数据。这些限制让你转而考虑环的视角。
为什么求和公式不适用于“查找重复数字”？
只有当重复值恰好出现两次时，用数组的和减去 1 + 2 + ... + n 才能得到这个重复值。这里，重复值可能会取代缺失值：在 [4, 2, 4, 1, 4] 中，差值是 15 减去 10 = 5，但数组中甚至没有这个值。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findDuplicate(nums):
# 在这里编写代码测试 #1
测试 #2
参数
nums = [2, 5, 1, 3, 5, 4]
预期输出
5