每日修仙尝试于9102年7/8.希望本座早日习得九阳神功，便可在灵石之路上助尔等一臂之力。
如题：
- 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例：
输入：{1,4,5,9,10,2,3,7,8,6,9}
输出：9
说明：
1、不能更改原数组（假设数组是只读的）。
2、只能使用额外的 O(1) 的空间。
3、时间复杂度小于 O(n2) 。
4、数组中只有一个重复的数字，但它可能不止重复出现一次。
解法一：
使用Set，这个就不用多BB了。但是一般使用这种解法，是不会有加分的，也就是说，你的面试者可能不会认可你。So，你可能要了解一哈“鸽子洞原理”（也称之为“抽屉原理”）了。
解法二：
弗洛伊德的乌龟和兔子（循环检测）。对于每对索引 i 和值 v_i而言，“下一个” v_j 位于索引 v_i处，我们可以将此问题减少到循环检测。
public class TortoiseAndHare {
public static void main(String[] args) {
int nums[] = {1,4,5,9,10,2,3,7,8,6,9};
int dup = findDuplicate(nums);
System.out.println(dup);
}
/**
* 弗洛伊德的乌龟和兔子
* <p>Title: findDuplicate</p>
* <p>Description:因为 nums 中的每个数字都在 1 和 n 之间，所以它必须指向存在的索引。此外，由于 0不能作为 nums 中的值出现，
nums[0] 不能作为循环的一部分 </p>
* @return
*/
public static int findDuplicate(int nums[]) {
int i = 0;
int tortoise = nums[0];
int hare = nums[0];
do {
tortoise = nums[tortoise];
hare = nums[nums[hare]];
System.out.print("第{"+(++i)+"}次");
System.out.print(" tortoise="+tortoise);
System.out.println(" hare="+hare);
}while(tortoise != hare);
return tortoise;
}
执行结果如下：
第{1}次 tortoise=4 hare=10
第{2}次 tortoise=10 hare=6
第{3}次 tortoise=9 hare=9
9
天地三清，道法无常。
溜溜球...
