## Description

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

Example 1:

Example 2:

Note:

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

## Solution

1. 只有一个节点的入度大于$1$（只有一个数字重复出现）；
2. 图中一定存在一个环（数组大小$n+1$）。

Python Code:

------ 本文结束------
0%