题目描述：

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate element must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

题目大意：

1. 不可以修改数组（假设数组是只读的）
2. 只能使用常数空间
3. 运行时间复杂度应该小于O(n2)
4. 数组中只存在一个重复数，但是可能重复多次

解题思路：

```这道题（据说）花费了计算机科学界的传奇人物Don Knuth 24小时才解出来。并且我只见过一个人（Keith Amling）用更短时间解出此题。

x_0     = k       (for some k)
x_1     = f(x_0)
x_2     = f(f(x_0))
...
x_{n+1} = f(x_n)

x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
^                       |
|                       |
+-----------------------+

x_{l'} = x_{2l'}

Floyd算法的一个关键点就是即使我们不明确知道c的值，依然可以在O(l')时间内找到值l'。思路如下。我们追踪两个值"slow"和"fast"，均从x_0开始。然后迭代计算

slow = f(slow)
fast = f(f(fast))

finder = f(finder)
slow   = f(slow)

Python代码：

``````class Solution(object):
def findDuplicate(self, nums):
# The "tortoise and hare" step.  We start at the end of the array and try
# to find an intersection point in the cycle.
slow = 0
fast = 0

# Keep advancing 'slow' by one step and 'fast' by two steps until they
# meet inside the loop.
while True:
slow = nums[slow]
fast = nums[nums[fast]]

if slow == fast:
break

# Start up another pointer from the end of the array and march it forward
# until it hits the pointer inside the array.
finder = 0
while True:
slow   = nums[slow]
finder = nums[finder]

# If the two hit, the intersection index is the duplicate element.
if slow == finder:
return slow
``````

“不允许修改数组” 与 “常数空间复杂度”这两个限制条件意味着：禁止排序，并且不能使用Map等数据结构

Python代码：

``````class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
low, high = 1, len(nums) - 1
while low <= high:
mid = (low + high) >> 1
cnt = sum(x <= mid for x in nums)
if cnt > mid:
high = mid - 1
else:
low = mid + 1
return low
``````

Pingbacks已关闭。

1. wei 发布于 2015年10月4日 07:03 #

这题我花了半天左右的时间想出解法，这么说我比Knuth解这道题的速度还快。。

2. 在线疯狂 发布于 2015年10月4日 11:07 #

忍不住赞一下！:)

3. Dean 发布于 2015年10月8日 13:59 #

I like how you can map every point to another point in the same array and form a cycle!

4. 志佳 发布于 2016年2月15日 12:44 #

二分搜索的方法，对于数组 [1,2,2,2,5,6,7], 找出来的结果是不对的？

5. j_ 发布于 2016年2月16日 10:24 #

有个问题，例如如果： f(xi) == f(f(xi)) 这个怎么避免？题目没有直接说明已定是P型数列，这个条件是怎么得出的？

6. 在线疯狂 发布于 2016年2月16日 11:21 #

我测试的结果是2

7. 在线疯狂 发布于 2016年2月16日 21:11 #

参考下这一段文字“由于数组元素范围1到n，因此不存在值为0的元素。从数组的第一个元素开始调用一次函数f之后，再也不会回到这里。这意味着第一个元素不会是环的一部分，但如果我们继续重复调用函数f，最终总会访问某个节点两次。从0节点开始的链条与环形相接，使得其形状一定是ρ型。”

8. j_ 发布于 2016年2月18日 00:56 #

thx, 这个是中文的分析，我可以理解，但是英文题目里面没有说从0开始。

9. j_ 发布于 2016年2月18日 02:44 #

题目没有说从值0开始吧？

10. 在线疯狂 发布于 2016年2月18日 20:43 #

嗯，题目描述的数据范围是从1到n

11. 洪北七 发布于 2016年4月21日 17:23 #

如果存放的元素不是1-n这样可以作为下标的值，而是比如任意数值，如何用类似的方法串联成一个P型链表呢？

12. 在线疯狂 发布于 2016年4月21日 17:40 #

题设这样修改的话，暂时没有想到常数空间复杂度，线性时间复杂度的解法。。。

13. Zenn 发布于 2016年5月6日 12:17 #

你这个数组有七个元素，按照题意，里面的元素取值范围应该是1～6，你这个输入本来就不对了啊。。

14. 在线疯狂 发布于 2016年5月10日 22:37 #

是的，我都没有注意到！:D

15. zuozhubinge 发布于 2016年8月26日 15:31 #

n+1个数每个数的范围是1-n，你这个例子最大的数应该是6不是7，违反题意了

16. 亦生 发布于 2016年9月2日 07:13 #

为什么我感觉第二种做法，时间复杂度也是 O(n) ?
第一次要扫描整个数组， n
第二次扫描一半的数组，n/2
第三次扫描四分之一的数组， n/4
n + n/2 + n/4 + ... ---> O(n)
是这样吗？

17. 在线疯狂 发布于 2016年9月2日 09:48 #

二分查找的复杂度是O(log n)，while循环内每一次线性查找的开销是O(n)，两者相乘，所以是O(n * log n)

18. 汤州林 发布于 2016年9月29日 21:30 #

楼主可以测试一下[1,2,2,3,5,6,7,8]或者是[1,2,3,4,6,7,7,8]必然有一个是错的。。。。

19. 在线疯狂 发布于 2016年10月1日 22:08 #

题目描述中：nums数组包含n+1个介于1-n之间的整数，所以你提供的测试用例不符合题目要求。

20. 我是游客 发布于 2016年10月30日 10:09 #

感谢！