每日修仙（一）

每日修仙尝试于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

天地三清，道法无常。
溜溜球...