题解链接

Leetcode 287.寻找重复数

题目描述

给定一个包含 $n + 1$ 个整数的数组 $nums$。

数组中的每个整数都在 $[1, n]$ 范围内。

已知数组中至少存在一个重复的整数。

假设 $nums$ 中只有一个重复的整数，请返回这个重复的数。

要求不能修改数组 $nums$，并且只能使用常量级 $O(1)$ 的额外空间。

输入描述

第一行输入一个整数 $n$，表示数组中数字的取值范围为 $[1, n]$。

第二行输入 $n + 1$ 个整数，表示数组 $nums$ 中的元素。

输出描述

输出一个整数，表示数组中重复的数字。

样例 $1$

输入

4
1 3 4 2 2

输出

2

样例 $2$

输入

4
3 1 3 4 2

输出

3

样例 $3$

输入

4
3 3 3 3 3

输出

3

数据范围

$1 <= n <= 10^5$

$nums.length == n + 1$

$1 <= nums[i] <= n$

$nums$ 中只有一个整数出现两次或多次，其余整数均只出现一次。